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 the minimum 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.

&nbsp;
Example 1:

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:

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:

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


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 40
	-107 &lt;= nums[i] &lt;= 107
	-109 &lt;= goal &lt;= 109


class Solution:
    def minAbsDifference(self, nums: List[int], goal: int) -> int:

        # When goal 0 we can just choose no elements 
        if goal == 0: return 0

        n = len(nums)
        mid = n // 2
        # Split the list in 2 parts and then find all possible subset sums 
        # T = O(2^n/2) to build all subset sums
        leftList = nums[:mid]
        leftSums = []
        rightList = nums[mid:]
        rightSums = []

        # T = O(2^n/2) to build all subset sums (we only consider half list)
        def buildSubsetSums(usedNums, numsToChooseFrom, ind, storeIn):
            if ind == len(numsToChooseFrom):
                # We also keep elements with sum 0 to deal with cases like this where we don't select nums
                # List: [1,2,3], Target: -7 (choosing no elements will give a sum close to goal)
                # We can also have cases where we want to take only 1 element from the list
                # so sum 0 for left and right list needs to be an option
                storeIn.append(sum(usedNums))
                return 

            usedNums.append(numsToChooseFrom[ind])
            buildSubsetSums(usedNums, numsToChooseFrom, ind+1, storeIn)
            usedNums.pop()
            buildSubsetSums(usedNums, numsToChooseFrom, ind+1, storeIn)


        buildSubsetSums([], leftList, 0, leftSums)
        buildSubsetSums([], rightList, 0, rightSums)
        # 2^n/2 log(2^n/2) = n/2 * 2^n/2 time to sort
        rightSums.sort()

        diff = float('inf')

        # Loop runs 2^n/2 times and inside binary search tale n/2 time 
        # So total time is n/2 * 2^n/2
        for leftSum in leftSums:
            complement = goal - leftSum
            # Bisect left takes log(2^n/2) = n/2 search time
            idx = bisect.bisect_left(rightSums, complement)

            for i in [idx - 1, idx, idx + 1]:
                if 0 <= i < len(rightSums):
                    finalSum = leftSum + rightSums[i]
                    diff = min(diff, abs(goal - finalSum))
        
        # Over all time complexity is - n/2 * 2^n/2
        # 1. Making subset sums will take - 2^n/2
        # 2. Sorting right list takes - 2^n/2 * n/2
        # 3. Iterating one list and finding closest complement in other 
        # takes n/2 * 2^n/2
        # Space will be O(n/2) for the list and call stack for building subset 
        return diff
class Solution {
    int[] arr;
    public int minAbsDifference(int[] nums, int goal) {
        arr = nums;
        int n = nums.length;
        
        
        List<Integer> first = new ArrayList<>();
        List<Integer> second = new ArrayList<>();
        
        generate(0,n/2,0, first); //generate all possible subset sums from half the array
        generate(n/2, n , 0, second);//generate all possible subset sums from the second half of the array
        
        
        Collections.sort(first);
        int ans = Integer.MAX_VALUE;
        
        
        for(int secondSetSum : second ) {
            int left = goal - secondSetSum; // How far off are we from the desired goal?
            
            if(first.get(0) > left) { // all subset sums from first half are too big => Choose the smallest
                ans = (int)(Math.min(ans, Math.abs((first.get(0) + secondSetSum) - goal)));
                continue;
            }
            if(first.get(first.size() - 1) < left) { // all subset sums from first half are too small => Choose the largest
                ans = (int)(Math.min(ans, Math.abs((first.get(first.size() - 1) + secondSetSum) - goal)));
                continue;
            }
            int pos = Collections.binarySearch(first, left);
            if(pos >= 0) // Exact match found! => first.get(pos) + secondSetSum == goal
                return 0;
            else        // If exact match not found, binarySearch in java returns (-(insertionPosition) - 1)
                pos = -1 * (pos + 1);
            int low = pos - 1;
            ans = (int)Math.min(ans, Math.abs(secondSetSum + first.get(low) - goal)); // Checking for the floor value (largest sum < goal)
            ans = (int)Math.min(ans, Math.abs(secondSetSum + first.get(pos) - goal)); //Checking for the ceiling value (smallest sum > goal)
        }
        return ans;
    }

    /**
    * Generating all possible subset sums. 2 choices at each index,i -> pick vs do not pick 
    */
    void generate(int i, int end, int sum, List<Integer> listOfSubsetSums) {
        if (i == end) {
            listOfSubsetSums.add(sum); //add
            return;
        }
        generate(i + 1, end, sum + arr[i], set);
        generate(i + 1, end, sum, set);
        
    }
    
    
    
}
class Solution {
public:
    void find(vector<int>&v, int i, int e, int sum, vector<int>&sumv){
        if(i==e){
            sumv.push_back(sum);
            return;
        }
        find(v,i+1,e,sum+v[i],sumv);
        find(v,i+1,e,sum,sumv);
    }

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

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

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

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

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

        sort(sumA.begin(),sumA.end());
        sort(sumB.begin(),sumB.end());

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

        int ans=INT_MAX;

        for(int i=0;i<sumA.size();i++){
            int s=sumA[i];
            int l=0;
            int r=sumB.size()-1;
            while(l<=r){
                int mid=l+(r-l)/2;
                int sum=s+sumB[mid];
                if(sum==goal)
                    return 0;
                ans=min(ans,abs(sum-goal));
                if(sum>goal){
                    r=mid-1;
                }
                else{
                    l=mid+1;
                }
            }
        }

        return ans;
    }
};
var minAbsDifference = function(nums, goal) {
    let mid = Math.floor(nums.length / 2);
    let part1 = nums.slice(0, mid), part2 = nums.slice(mid);

    function findSubsetSums(arr, set, idx = 0, sum = 0) {
        if (idx === arr.length) return set.add(sum);
        findSubsetSums(arr, set, idx + 1, sum);
        findSubsetSums(arr, set, idx + 1, sum + arr[idx]);
    }

    let sum1 = new Set(), sum2 = new Set();
    findSubsetSums(part1, sum1);
    findSubsetSums(part2, sum2);

    sum1 = [...sum1.values()];
    sum2 = [...sum2.values()];
    sum2.sort((a, b) => a - b);

    let min = Infinity;
    for (let num1 of sum1) {
        let l = 0, r = sum2.length - 1;
        while (l <= r) {
            let mid = l + Math.floor((r - l) / 2);
            let num2 = sum2[mid];
            min = Math.min(min, Math.abs(num1 + num2 - goal));
            if (num1 + num2 < goal) l = mid + 1;
            else r = mid - 1;
        }
    }
    return min;
};
Closest Subsequence Sum