Skip to content

1755. Closest Subsequence Sum 👍

  • Time: $O(n \cdot 2^{n/2})$
  • Space: $O(2^{n/2})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int minAbsDifference(vector<int>& nums, int goal) {
    const int n = nums.size() / 2;
    const vector<int> lNums(nums.begin(), nums.begin() + n);
    const vector<int> rNums(nums.begin() + n, nums.end());
    int ans = INT_MAX;
    vector<int> lSums;
    vector<int> rSums;

    dfs(lNums, 0, 0, lSums);
    dfs(rNums, 0, 0, rSums);
    sort(rSums.begin(), rSums.end());

    for (const int lSum : lSums) {
      const int i = firstGreaterEqual(rSums, goal - lSum);
      if (i < rSums.size())  // 2^n
        ans = min(ans, abs(goal - lSum - rSums[i]));
      if (i > 0)
        ans = min(ans, abs(goal - lSum - rSums[i - 1]));
    }

    return ans;
  }

 private:
  void dfs(const vector<int>& A, int i, int path, vector<int>& sums) {
    if (i == A.size()) {
      sums.push_back(path);
      return;
    }
    dfs(A, i + 1, path + A[i], sums);
    dfs(A, i + 1, path, sums);
  }

  int firstGreaterEqual(const vector<int>& A, int target) {
    return lower_bound(A.begin(), A.end(), target) - A.begin();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
  public int minAbsDifference(int[] nums, int goal) {
    final int n = nums.length / 2;
    final int[] lNums = Arrays.copyOfRange(nums, 0, n);
    final int[] rNums = Arrays.copyOfRange(nums, n, nums.length);
    int ans = Integer.MAX_VALUE;
    List<Integer> lSums = new ArrayList<>();
    List<Integer> rSums = new ArrayList<>();

    dfs(lNums, 0, 0, lSums);
    dfs(rNums, 0, 0, rSums);
    Collections.sort(rSums);

    for (final int lSum : lSums) {
      final int i = firstGreaterEqual(rSums, goal - lSum);
      if (i < rSums.size()) // 2^n
        ans = Math.min(ans, Math.abs(goal - lSum - rSums.get(i)));
      if (i > 0)
        ans = Math.min(ans, Math.abs(goal - lSum - rSums.get(i - 1)));
    }

    return ans;
  }

  private void dfs(int[] A, int i, int path, List<Integer> sums) {
    if (i == A.length) {
      sums.add(path);
      return;
    }
    dfs(A, i + 1, path + A[i], sums);
    dfs(A, i + 1, path, sums);
  }

  private int firstGreaterEqual(List<Integer> A, int target) {
    int l = 0;
    int r = A.size();
    while (l < r) {
      final int m = (l + r) / 2;
      if (A.get(m) >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def minAbsDifference(self, nums: List[int], goal: int) -> int:
    n = len(nums) // 2
    ans = math.inf
    lSums = []
    rSums = []

    def dfs(A: List[int], i: int, path: int, sums: List[int]) -> None:
      if i == len(A):
        sums.append(path)
        return
      dfs(A, i + 1, path + A[i], sums)
      dfs(A, i + 1, path, sums)

    dfs(nums[:n], 0, 0, lSums)
    dfs(nums[n:], 0, 0, rSums)
    rSums.sort()

    for lSum in lSums:
      i = bisect_left(rSums, goal - lSum)
      if i < len(rSums):  # 2^n
        ans = min(ans, abs(goal - lSum - rSums[i]))
      if i > 0:
        ans = min(ans, abs(goal - lSum - rSums[i - 1]))

    return ans