1755. Closest Subsequence Sum

一刷 06/2022

Version #1 Two Half Combination + TreeSet

Time - n/2*2^(n/2)*lg(2^(n/2)) = n^2 * 2^(n/2) 

Space O(n * 2^(n/2))

Runtime: 1507 ms, faster than 25.00% of Java online submissions for Closest Subsequence Sum.

Memory Usage: 150.8 MB, less than 48.44% of Java online submissions for Closest Subsequence Sum.

class Solution {

    public int minAbsDifference(int[] nums, int goal) {

        // Select half of the nums, compute all the combinations of those nums

        // System.out.printf("%s\n", combination(nums, 0, 1).toString());

        List<Integer> firstHalfComb = combination(nums, 0, nums.length / 2);

        List<Integer> secondHalfComb = combination(nums, nums.length / 2 + 1, nums.length - 1);

        TreeSet<Integer> secondHalf = new TreeSet<>(secondHalfComb);

        int min = Integer.MAX_VALUE;

        for (Integer comb : firstHalfComb) {

            int diff = goal - comb;

            if (secondHalfComb.size() == 0) {

                min = Math.min(min, Math.abs(diff));

                continue;

            }

            Integer h = secondHalf.ceiling(diff);

            if (h != null) {

                min = Math.min(min, Math.abs(h - diff));

            }

            Integer l = secondHalf.floor(diff);

            if (l != null) {

                min = Math.min(min, Math.abs(l - diff));

            }

            if (min == 0) {

                break;

            }

        }

        return min;

    }

    

    private List<Integer> combination(int[] nums, int start, int end) {

        if (end < start) {

            return new ArrayList<>();

        }

        // [start, end] inclusive -> end + start + 1 numbers

        int n = end - start + 1;

        int max = 1 << n;

        // System.out.printf("max=%d\n", max);

        List<Integer> result = new ArrayList<>();

        for (int mask = 0; mask < max; mask++) {

            // System.out.printf("mask:%d\n", mask);

            int sum = 0;

            for (int shift = 0; shift < n; shift++) {

                if (((mask >> shift) & 1) != 0) {

                    sum += nums[start + shift];

                }

            }

            result.add(sum);

        }

        return result;

    }

}