Combination Sum

1package pkg5leetcode.blind75;2 3/*4 * Combination Sum | LC 395 * APPROACH: Backtracking with reuse; sort and prune early.6 * COMPLEXITY: Time O(2^n) worst case, Space O(target)7 */8import java.util.*;9 10public class blind75_LC39CombinationSum {11    static List<List<Integer>> combinationSum(int[] candidates, int target) {12        Arrays.sort(candidates);13        List<List<Integer>> res = new ArrayList<>();14        backtrack(candidates, target, 0, new ArrayList<>(), res);15        return res;16    }17 18    static void backtrack(int[] c, int rem, int start, List<Integer> path, List<List<Integer>> res) {19        if (rem == 0) { res.add(new ArrayList<>(path)); return; }20        for (int i = start; i < c.length; i++) {21            if (c[i] > rem) break;22            path.add(c[i]);23            backtrack(c, rem - c[i], i, path, res);24            path.remove(path.size() - 1);25        }26    }27 28    public static void main(String[] args) {29        List<List<Integer>> r = combinationSum(new int[]{2, 3, 6, 7}, 7);30        check(r.size() == 2, "size");31        check(r.contains(Arrays.asList(2, 2, 3)), "combo1");32        check(r.contains(Arrays.asList(7)), "combo2");33        System.out.println("all tests passed");34    }35 36    static void check(boolean cond, String name) {37        if (!cond) throw new AssertionError("FAILED: " + name);38        System.out.println("  PASS " + name);39    }40}