最接近目标值的子序列和

/* 
 * 思路：
 * 1. 使用流来生成所有可能的子序列和。
 * 2. 将数组分成两部分，分别处理。
 * 3. 使用流和二分查找合并结果，找到绝对差最小的值。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int minAbsDifference(int[] nums, int goal) {
        int n = nums.length;
        List<Integer> leftSums = generateSums(Arrays.copyOfRange(nums, 0, n / 2));
        List<Integer> rightSums = generateSums(Arrays.copyOfRange(nums, n / 2, n));
        Collections.sort(rightSums);

        return leftSums.stream()
            .mapToInt(sum -> {
                int remaining = goal - sum;
                int idx = Collections.binarySearch(rightSums, remaining);
                if (idx >= 0) {
                    return 0;
                } else {
                    idx = -idx - 1;
                    int diff1 = idx < rightSums.size() ? Math.abs(remaining - rightSums.get(idx)) : Integer.MAX_VALUE;
                    int diff2 = idx > 0 ? Math.abs(remaining - rightSums.get(idx - 1)) : Integer.MAX_VALUE;
                    return Math.min(diff1, diff2);
                }
            })
            .min()
            .orElse(Integer.MAX_VALUE);
    }

    private List<Integer> generateSums(int[] nums) {
        return IntStream.range(0, 1 << nums.length)
            .mapToObj(mask -> IntStream.range(0, nums.length)
                .filter(i -> (mask & (1 << i)) != 0)
                .map(i -> nums[i])
                .sum())
            .collect(Collectors.toList());
    }
}