hardBit ManipulationAI-applied~40 min
Subset of Feature Weights Closest to a Budget
From a pool of signed feature weights, select any subset whose total is as close as possible to a target compute budget. Report the minimum absolute gap between the chosen subset sum and the goal.
Problem
Given an integer array nums and an integer goal, choose any subsequence (possibly empty) whose sum is as close to goal as possible. Return the minimum possible value of abs(sum(subsequence) - goal).
Input
An integer array nums and an integer goal.
Output
An integer: the minimum achievable absolute difference.
Constraints
- 1 <= nums.length <= 40
- -10^7 <= nums[i] <= 10^7
- -10^9 <= goal <= 10^9
Examples
Example 1
Input
nums = [5,-7,3,5], goal = 6
Output
0
The subset {5,-7,3,5} sums to 6, an exact match.
Example 2
Input
nums = [7,-9,15,-2], goal = -5
Output
1
The closest reachable subset sum differs from -5 by 1.