Closest Subsequence Sum LeetCode solution in C++

1
class Solution {
2
 public:
3
  void find(vector<int> &v, int i, int e, int sum, vector<int> &sumv) {
4
    if (i == e) {
5
      sumv.push_back(sum);
6
      return;
7
    }
8
    find(v, i + 1, e, sum + v[i], sumv);
9
    find(v, i + 1, e, sum, sumv);
10
  }
11

12
  int minAbsDifference(vector<int> &nums, int goal) {
13
    int n = nums.size();
14

15
    // Step 1: Divide nums into 2 subarrays of size n/2 and n-n/2
16

17
    vector<int> A, B;
18
    for (int i = 0; i < n / 2; i++) A.push_back(nums[i]);
19
    for (int i = n / 2; i < n; i++) B.push_back(nums[i]);
20

21
    // Step 2: Find all possible subset sums of A and B
22

23
    vector<int> sumA, sumB;
24
    find(A, 0, A.size(), 0, sumA);
25
    find(B, 0, B.size(), 0, sumB);
26

27
    sort(sumA.begin(), sumA.end());
28
    sort(sumB.begin(), sumB.end());
29

30
    // Step 3: Find combinations from sumA & sumB such that abs(sum-goal) is
31
    // minimized
32

33
    int ans = INT_MAX;
34

35
    for (int i = 0; i < sumA.size(); i++) {
36
      int s = sumA[i];
37
      int l = 0;
38
      int r = sumB.size() - 1;
39
      while (l <= r) {
40
        int mid = l + (r - l) / 2;
41
        int sum = s + sumB[mid];
42
        if (sum == goal) return 0;
43
        ans = min(ans, abs(sum - goal));
44
        if (sum > goal) {
45
          r = mid - 1;
46
        } else {
47
          l = mid + 1;
48
        }
49
      }
50
    }
51

52
    return ans;
53
  }
54
};