Lintcode - Combination Sum II

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

Each number in_C_may only be used once in the combination.

Notice

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

Example

Given candidate set[10,1,6,7,2,1,5]and target8,

A solution set is:

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

Analysis: DFS is usually needed when to list out all the valid solutions . Because the problem is asking for elements in the combinations to be non-descending order, the candidates collection should be sorted in ascending order first. Also the solution set must no contain duplication combinations, then some numbers should be skipped when condition is met,

This occurs in two scenarios.

First scenario: e.g. [1,1,1,3], in the loop of the 1st 1, in its recursion, the 3rd 1 should be skipped when the 2nd 1 has been exhaustively used in looking for a solution in combination with the 1st 1.

Second scenario: e.g. [1,1,1,3], for the outermost loop, the 2nd 1 should be skipped because the 1st one has been exhaustively used in looking for a solution in combination with all the elements in the collection.

    public List<List<Integer>> combinationSum2(int[] num, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (num.length == 0) {
            return result;
        }

        Arrays.sort(num);
        helper(num, 0, target, new ArrayList<Integer>(), result);
        return result;
    }

    public void helper(int[] num, int index, int target, List<Integer> path, List<List<Integer>> result){
        if (target == 0){            
            result.add(new ArrayList<Integer>(path));
            return;
        }

        for (int i = index; i < num.length; i++){
            if (i != index && num[i] == num[i - 1]){                
                continue;
            }

            if (target < num[i]){
                break;
            }

            path.add(num[i]);
            helper(num, i + 1, target - num[i], path, result);
            path.remove(path.size() - 1);
        }        
    }