class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int n = candidates.length;
        int[] dp = new int[target+1];

        Map<Integer, List<List<Integer>>> combs = new HashMap<>();
        for (int w = 0; w <= target; w++) {
            combs.putIfAbsent(w, new ArrayList<>());
        }

        List<Integer> empty = new ArrayList<>();
        combs.get(0).add(empty);

        for (int i = 0; i < n; i++) {
            for (int w = 0; w <= target; w++) {
                if (w >= candidates[i]) {
                    List<List<Integer>> prev = combs.get(w-candidates[i]);
                    for (List<Integer> x : prev) {
                        x.add(candidates[i]);
                        combs.get(w).add(new ArrayList<>(x));
                        x.remove(x.size()-1);
                    }
                }
            }
        }

        return combs.get(target);
    }
}

class Solution {
    private List<List<Integer>> answer;

    private void backtrack(int start, int[] candidates, int target, List<Integer> curr) {
        if (target == 0) {
            answer.add(new ArrayList<>(curr));
            return;
        }

        int n = candidates.length;

        for (int i = start; i < n; i++) {
            int c = candidates[i];
            if (target - c >= 0) {
                curr.add(c);
                backtrack(i, candidates, target - c, curr); // start at i
                curr.remove(curr.size()-1);
            }
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        answer = new ArrayList<>();
        List<Integer> curr = new ArrayList<>();
        backtrack(0, candidates, target, curr);
        return answer;
    }
}