Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Given candidate set 10,1,2,7,6,1,5 and target 8,

A solution set is:

[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Method:

Because we can't reuse elements, every time we go down the recursion tree, we increase index by one. Also we deduplicate when we add the new solution to result list.

Solution:

Time: O(n^k), k = target/min number
Space: O(n^k)

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(ArrayList<Integer> a, int b) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> current = new ArrayList<>();
        Collections.sort(a);
        helper(result, current, a, 0, b, 0);
        return result;
    }
    
    private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> current, ArrayList<Integer> a, int sum, int b, int index) {
        if (sum > b) {
            return;
        }
        if (sum == b) {
            ArrayList<Integer> solution = new ArrayList<>(current);
            if (!result.isEmpty() && result.get(result.size() - 1).equals(solution)) {
                return;
            } else {
                result.add(solution);
            }
            return;
        }
        for (int i = index; i < a.size(); i ++) {
            int val = a.get(i);
            current.add(val);
            helper(result, current, a, sum + val, b, i + 1);
            current.remove(current.size() - 1);
        }
    }
}