/**
* @param {number[]} nums
* @param {number} goal
* @return {number}
*/
var minAbsDifference = function (nums, goal) {
const mid = nums.length >> 1;
// divide |nums| into two halves
// calculate sums of all possible subsets repectively
const leftSums = [];
dfs(nums, 0, mid, 0, leftSums);
const rightSums = [];
dfs(nums, mid, nums.length, 0, rightSums);
// we need to choose one value from |leftSums| and |rightSums| respectively
// the |x| and |y| chosen should sum closest to |goal|
// first sort |leftSums| for using binary search to find target
leftSums.sort((a, b) => a - b);
// now iterate through |rightSums|
// for each sum |x| from |rightSums|, go find the value closest to |goal-x| in |leftSums|, let's call it |closest|
// idealy |closest| will be equal to |goal-x|, which makes the total subset sum equal to |goal|
// if not so lucky, we pick the closest |closest| over the iteration
let minDiff = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < rightSums.length; i++) {
const x = rightSums[i];
const target = goal - x;
const closest = findClosest(leftSums, target);
const diff = Math.abs(target - closest);
minDiff = Math.min(diff, minDiff)
}
return minDiff
// ******************************************
function dfs(nums, start, end, currentSum, bucket) {
if (start == end) {
bucket.push(currentSum);
return;
}
dfs(nums, start + 1, end, currentSum + nums[start], bucket);
dfs(nums, start + 1, end, currentSum, bucket);
}
function findClosest(list, target) {
let l = 0,
r = list.length - 1,
m = 0;
while (l <= r) {
m = ((r - l) >> 1) + l;
if (list[m] == target) return target
if (list[m] < target) l = m + 1
else r = m - 1
}
if (l >= list.length) return list[r];
if (r < 0) return list[l];
return Math.abs(list[l] - target) < Math.abs(list[r] - target) ? list[l] : list[r];
}
};