Closest Subsequence Sum LeetCode solution in Java

1
class Solution {
2
  int[] arr;
3

4
  public int minAbsDifference(int[] nums, int goal) {
5
    arr = nums;
6
    int n = nums.length;
7

8
    List<Integer> first = new ArrayList<>();
9
    List<Integer> second = new ArrayList<>();
10

11
    generate(0, n / 2, 0, first); // generate all possible subset sums from half the array
12
    generate(
13
        n / 2, n, 0, second); // generate all possible subset sums from the second half of the array
14

15
    Collections.sort(first);
16
    int ans = Integer.MAX_VALUE;
17

18
    for (int secondSetSum : second) {
19
      int left = goal - secondSetSum; // How far off are we from the desired goal?
20

21
      if (first.get(0)
22
          > left) { // all subset sums from first half are too big => Choose the smallest
23
        ans = (int) (Math.min(ans, Math.abs((first.get(0) + secondSetSum) - goal)));
24
        continue;
25
      }
26
      if (first.get(first.size() - 1)
27
          < left) { // all subset sums from first half are too small => Choose the largest
28
        ans = (int) (Math.min(ans, Math.abs((first.get(first.size() - 1) + secondSetSum) - goal)));
29
        continue;
30
      }
31
      int pos = Collections.binarySearch(first, left);
32
      if (pos >= 0) // Exact match found! => first.get(pos) + secondSetSum == goal
33
      return 0;
34
      else // If exact match not found, binarySearch in java returns (-(insertionPosition) - 1)
35
      pos = -1 * (pos + 1);
36
      int low = pos - 1;
37
      ans =
38
          (int)
39
              Math.min(
40
                  ans,
41
                  Math.abs(
42
                      secondSetSum
43
                          + first.get(low)
44
                          - goal)); // Checking for the floor value (largest sum < goal)
45
      ans =
46
          (int)
47
              Math.min(
48
                  ans,
49
                  Math.abs(
50
                      secondSetSum
51
                          + first.get(pos)
52
                          - goal)); // Checking for the ceiling value (smallest sum > goal)
53
    }
54
    return ans;
55
  }
56

57
  /** Generating all possible subset sums. 2 choices at each index,i -> pick vs do not pick */
58
  void generate(int i, int end, int sum, List<Integer> listOfSubsetSums) {
59
    if (i == end) {
60
      listOfSubsetSums.add(sum); // add
61
      return;
62
    }
63
    generate(i + 1, end, sum + arr[i], set);
64
    generate(i + 1, end, sum, set);
65
  }
66
}