Problem

You are given an integer array nums and an integer goal.

You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal. That is, if the sum of the subsequence’s elements is sum, then you want to minimize the absolute difference abs(sum - goal).

Return theminimum possible value of abs(sum - goal).

Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.

Examples

Example 1

1
2
3
4

Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.

Example 2

1
2
3
4

Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: Choose the subsequence [7,-9,-2], with a sum of -4.
The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.

Example 3

1
2

Input: nums = [1,2,3], goal = -7
Output: 7

Constraints

  • 1 <= nums.length <= 40
  • -10^7 <= nums[i] <= 10^7
  • -109 <= goal <= 10^9

Solution

Method 1 – Meet in the Middle

Intuition

Since the array is small (≤ 40), we can split it into two halves and enumerate all possible subsequence sums for each half. For each sum in the first half, we can use binary search in the second half to find the sum that, when combined, is closest to the goal.

Approach

  1. Split nums into two halves: A and B.
  2. Generate all possible subset sums for both halves using bitmasking.
  3. Sort the list of sums for the second half.
  4. For each sum in the first half, use binary search to find the sum in the second half that makes the total closest to goal.
  5. Track and return the minimum absolute difference found.

Code

 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

class Solution {
public:
    int minAbsDifference(vector<int>& nums, int goal) {
        int n = nums.size(), n1 = n / 2, n2 = n - n1;
        vector<int> A, B;
        for (int i = 0; i < n1; ++i) A.push_back(nums[i]);
        for (int i = n1; i < n; ++i) B.push_back(nums[i]);
        vector<int> sa, sb;
        for (int mask = 0; mask < (1 << n1); ++mask) {
            int s = 0;
            for (int i = 0; i < n1; ++i) if (mask & (1 << i)) s += A[i];
            sa.push_back(s);
        }
        for (int mask = 0; mask < (1 << n2); ++mask) {
            int s = 0;
            for (int i = 0; i < n2; ++i) if (mask & (1 << i)) s += B[i];
            sb.push_back(s);
        }
        sort(sb.begin(), sb.end());
        int ans = abs(goal);
        for (int x : sa) {
            int t = goal - x;
            auto it = lower_bound(sb.begin(), sb.end(), t);
            if (it != sb.end()) ans = min(ans, abs(x + *it - goal));
            if (it != sb.begin()) ans = min(ans, abs(x + *(--it) - goal));
        }
        return ans;
    }
};
 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

func minAbsDifference(nums []int, goal int) int {
    n := len(nums)
    n1 := n / 2
    n2 := n - n1
    A := nums[:n1]
    B := nums[n1:]
    sa := []int{}
    sb := []int{}
    for mask := 0; mask < 1<<n1; mask++ {
        s := 0
        for i := 0; i < n1; i++ {
            if mask&(1<<i) != 0 {
                s += A[i]
            }
        }
        sa = append(sa, s)
    }
    for mask := 0; mask < 1<<n2; mask++ {
        s := 0
        for i := 0; i < n2; i++ {
            if mask&(1<<i) != 0 {
                s += B[i]
            }
        }
        sb = append(sb, s)
    }
    sort.Ints(sb)
    ans := abs(goal)
    for _, x := range sa {
        t := goal - x
        idx := sort.SearchInts(sb, t)
        if idx < len(sb) {
            ans = min(ans, abs(x+sb[idx]-goal))
        }
        if idx > 0 {
            ans = min(ans, abs(x+sb[idx-1]-goal))
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if a < b { return a } else { return b } }
 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

class Solution {
    public int minAbsDifference(int[] nums, int goal) {
        int n = nums.length, n1 = n / 2, n2 = n - n1;
        int[] A = Arrays.copyOfRange(nums, 0, n1);
        int[] B = Arrays.copyOfRange(nums, n1, n);
        List<Integer> sa = new ArrayList<>(), sb = new ArrayList<>();
        for (int mask = 0; mask < (1 << n1); mask++) {
            int s = 0;
            for (int i = 0; i < n1; i++) if ((mask & (1 << i)) != 0) s += A[i];
            sa.add(s);
        }
        for (int mask = 0; mask < (1 << n2); mask++) {
            int s = 0;
            for (int i = 0; i < n2; i++) if ((mask & (1 << i)) != 0) s += B[i];
            sb.add(s);
        }
        Collections.sort(sb);
        int ans = Math.abs(goal);
        for (int x : sa) {
            int t = goal - x;
            int idx = Collections.binarySearch(sb, t);
            if (idx < 0) idx = -idx - 1;
            if (idx < sb.size()) ans = Math.min(ans, Math.abs(x + sb.get(idx) - goal));
            if (idx > 0) ans = Math.min(ans, Math.abs(x + sb.get(idx - 1) - goal));
        }
        return ans;
    }
}
 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

class Solution {
    fun minAbsDifference(nums: IntArray, goal: Int): Int {
        val n = nums.size
        val n1 = n / 2
        val n2 = n - n1
        val A = nums.sliceArray(0 until n1)
        val B = nums.sliceArray(n1 until n)
        val sa = mutableListOf<Int>()
        val sb = mutableListOf<Int>()
        for (mask in 0 until (1 shl n1)) {
            var s = 0
            for (i in 0 until n1) if ((mask and (1 shl i)) != 0) s += A[i]
            sa.add(s)
        }
        for (mask in 0 until (1 shl n2)) {
            var s = 0
            for (i in 0 until n2) if ((mask and (1 shl i)) != 0) s += B[i]
            sb.add(s)
        }
        sb.sort()
        var ans = kotlin.math.abs(goal)
        for (x in sa) {
            val t = goal - x
            val idx = sb.binarySearch(t).let { if (it < 0) -it - 1 else it }
            if (idx < sb.size) ans = minOf(ans, kotlin.math.abs(x + sb[idx] - goal))
            if (idx > 0) ans = minOf(ans, kotlin.math.abs(x + sb[idx - 1] - goal))
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def minAbsDifference(self, nums: list[int], goal: int) -> int:
        from bisect import bisect_left
        n = len(nums)
        n1 = n // 2
        n2 = n - n1
        A, B = nums[:n1], nums[n1:]
        sa = [sum(A[i] for i in range(n1) if mask & (1 << i)) for mask in range(1 << n1)]
        sb = [sum(B[i] for i in range(n2) if mask & (1 << i)) for mask in range(1 << n2)]
        sb.sort()
        ans = abs(goal)
        for x in sa:
            t = goal - x
            idx = bisect_left(sb, t)
            if idx < len(sb):
                ans = min(ans, abs(x + sb[idx] - goal))
            if idx > 0:
                ans = min(ans, abs(x + sb[idx - 1] - goal))
        return ans
 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

impl Solution {
    pub fn min_abs_difference(nums: Vec<i32>, goal: i32) -> i32 {
        let n = nums.len();
        let n1 = n / 2;
        let n2 = n - n1;
        let a = &nums[..n1];
        let b = &nums[n1..];
        let mut sa = vec![];
        let mut sb = vec![];
        for mask in 0..(1 << n1) {
            let mut s = 0;
            for i in 0..n1 {
                if (mask & (1 << i)) != 0 {
                    s += a[i];
                }
            }
            sa.push(s);
        }
        for mask in 0..(1 << n2) {
            let mut s = 0;
            for i in 0..n2 {
                if (mask & (1 << i)) != 0 {
                    s += b[i];
                }
            }
            sb.push(s);
        }
        sb.sort();
        let mut ans = goal.abs();
        for &x in &sa {
            let t = goal - x;
            let idx = sb.binary_search(&t).unwrap_or_else(|i| i);
            if idx < sb.len() {
                ans = ans.min((x + sb[idx] - goal).abs());
            }
            if idx > 0 {
                ans = ans.min((x + sb[idx - 1] - goal).abs());
            }
        }
        ans
    }
}
 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

class Solution {
    minAbsDifference(nums: number[], goal: number): number {
        const n = nums.length, n1 = Math.floor(n / 2), n2 = n - n1;
        const A = nums.slice(0, n1), B = nums.slice(n1);
        const sa: number[] = [], sb: number[] = [];
        for (let mask = 0; mask < (1 << n1); mask++) {
            let s = 0;
            for (let i = 0; i < n1; i++) if (mask & (1 << i)) s += A[i];
            sa.push(s);
        }
        for (let mask = 0; mask < (1 << n2); mask++) {
            let s = 0;
            for (let i = 0; i < n2; i++) if (mask & (1 << i)) s += B[i];
            sb.push(s);
        }
        sb.sort((a, b) => a - b);
        let ans = Math.abs(goal);
        for (const x of sa) {
            const t = goal - x;
            let l = 0, r = sb.length - 1;
            while (l < r) {
                const m = Math.floor((l + r) / 2);
                if (sb[m] < t) l = m + 1;
                else r = m;
            }
            ans = Math.min(ans, Math.abs(x + sb[l] - goal));
            if (l > 0) ans = Math.min(ans, Math.abs(x + sb[l - 1] - goal));
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(2^(n/2) * log(2^(n/2)))
  • 🧺 Space complexity: O(2^(n/2))