Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1755.html

1755. Closest Subsequence Sum

Level

Hard

Description

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.

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

Constraints:

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

Solution

Divide nums of two parts that have lengths differ by at most 1. For each part, calculate all subsets’ sums of elements, and use a list to store the sums of all subsets. After the two lists are obtained, sort the two lists and find the closest sum of two elements from the two list (one from each list). Use two pointers to do this. After the closest sum is found, calculate the minimum absolute difference.

  • class Solution {
        public int minAbsDifference(int[] nums, int goal) {
            if (goal == 0)
                return 0;
            Arrays.sort(nums);
            int length = nums.length;
            int halfLength = length / 2;
            List<Integer> list1 = new ArrayList<Integer>();
            list1.add(0);
            List<Integer> list2 = new ArrayList<Integer>();
            list2.add(0);
            for (int i = 0; i < halfLength; i++) {
                int num = nums[i];
                int size = list1.size();
                for (int j = 0; j < size; j++)
                    list1.add(list1.get(j) + num);
            }
            for (int i = halfLength; i < length; i++) {
                int num = nums[i];
                int size = list2.size();
                for (int j = 0; j < size; j++)
                    list2.add(list2.get(j) + num);
            }
            Collections.sort(list1);
            Collections.sort(list2);
            int minDifference = Integer.MAX_VALUE;
            int size1 = list1.size(), size2 = list2.size();
            int pointer1 = 0, pointer2 = size2 - 1;
            while (pointer1 < size1 && pointer2 >= 0) {
                int curSum = list1.get(pointer1) + list2.get(pointer2);
                int curDifference = curSum - goal;
                minDifference = Math.min(minDifference, Math.abs(curDifference));
                if (curDifference == 0)
                    return 0;
                else if (curDifference < 0)
                    pointer1++;
                else
                    pointer2--;
            }
            return minDifference;
        }
    }
    
    ############
    
    class Solution {
        public int minAbsDifference(int[] nums, int goal) {
            int n = nums.length;
            List<Integer> lsum = new ArrayList<>();
            List<Integer> rsum = new ArrayList<>();
            dfs(nums, lsum, 0, n / 2, 0);
            dfs(nums, rsum, n / 2, n, 0);
    
            rsum.sort(Integer::compareTo);
            int res = Integer.MAX_VALUE;
    
            for (Integer x : lsum) {
                int target = goal - x;
                int left = 0, right = rsum.size();
                while (left < right) {
                    int mid = (left + right) >> 1;
                    if (rsum.get(mid) < target) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                if (left < rsum.size()) {
                    res = Math.min(res, Math.abs(target - rsum.get(left)));
                }
                if (left > 0) {
                    res = Math.min(res, Math.abs(target - rsum.get(left - 1)));
                }
            }
    
            return res;
        }
    
        private void dfs(int[] nums, List<Integer> sum, int i, int n, int cur) {
            if (i == n) {
                sum.add(cur);
                return;
            }
    
            dfs(nums, sum, i + 1, n, cur);
            dfs(nums, sum, i + 1, n, cur + nums[i]);
        }
    }
    
    
  • class Solution:
        def minAbsDifference(self, nums: List[int], goal: int) -> int:
            n = len(nums)
            left = set()
            right = set()
    
            self.getSubSeqSum(0, 0, nums[: n // 2], left)
            self.getSubSeqSum(0, 0, nums[n // 2 :], right)
    
            result = inf
            right = sorted(right)
            rl = len(right)
    
            for l in left:
                remaining = goal - l
                idx = bisect_left(right, remaining)
    
                if idx < rl:
                    result = min(result, abs(remaining - right[idx]))
    
                if idx > 0:
                    result = min(result, abs(remaining - right[idx - 1]))
    
            return result
    
        def getSubSeqSum(self, i: int, curr: int, arr: List[int], result: Set[int]):
            if i == len(arr):
                result.add(curr)
                return
    
            self.getSubSeqSum(i + 1, curr, arr, result)
            self.getSubSeqSum(i + 1, curr + arr[i], arr, result)
    
    
    
  • class Solution {
    public:
        int minAbsDifference(vector<int>& nums, int goal) {
            int n = nums.size();
            vector<int> lsum;
            vector<int> rsum;
            dfs(nums, lsum, 0, n / 2, 0);
            dfs(nums, rsum, n / 2, n, 0);
    
            sort(rsum.begin(), rsum.end());
            int res = INT_MAX;
    
            for (int x : lsum) {
                int target = goal - x;
                int left = 0, right = rsum.size();
                while (left < right) {
                    int mid = (left + right) >> 1;
                    if (rsum[mid] < target) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                if (left < rsum.size()) {
                    res = min(res, abs(target - rsum[left]));
                }
                if (left > 0) {
                    res = min(res, abs(target - rsum[left - 1]));
                }
            }
    
            return res;
        }
    
    private:
        void dfs(vector<int>& nums, vector<int>& sum, int i, int n, int cur) {
            if (i == n) {
                sum.emplace_back(cur);
                return;
            }
    
            dfs(nums, sum, i + 1, n, cur);
            dfs(nums, sum, i + 1, n, cur + nums[i]);
        }
    };
    
    
  • func minAbsDifference(nums []int, goal int) int {
    	n := len(nums)
    	lsum := make([]int, 0)
    	rsum := make([]int, 0)
    
    	dfs(nums[:n/2], &lsum, 0, 0)
    	dfs(nums[n/2:], &rsum, 0, 0)
    
    	sort.Ints(rsum)
    	res := math.MaxInt32
    
    	for _, x := range lsum {
    		t := goal - x
    		l, r := 0, len(rsum)
    		for l < r {
    			m := int(uint(l+r) >> 1)
    			if rsum[m] < t {
    				l = m + 1
    			} else {
    				r = m
    			}
    		}
    		if l < len(rsum) {
    			res = min(res, abs(t-rsum[l]))
    		}
    		if l > 0 {
    			res = min(res, abs(t-rsum[l-1]))
    		}
    	}
    
    	return res
    }
    
    func dfs(nums []int, sum *[]int, i, cur int) {
    	if i == len(nums) {
    		*sum = append(*sum, cur)
    		return
    	}
    
    	dfs(nums, sum, i+1, cur)
    	dfs(nums, sum, i+1, cur+nums[i])
    }
    
    func min(x, y int) int {
    	if x < y {
    		return x
    	}
    	return y
    }
    
    func abs(x int) int {
    	if x < 0 {
    		return -x
    	}
    	return x
    }
    
    

All Problems

All Solutions