Leetcode: 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.

Note:

• 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.

For example, 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] 

Understand the problem:
The problem is very similar to the last question, but each number in C can only be used once in the combination. So the solution is still DFS. 

Solution:

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) {
            return result;
        }
        
        Arrays.sort(num);
        
        combinationSumHelper(num, target, 0, 0, new ArrayList<Integer>(), result);
        
        return result;
    }
    
    private void combinationSumHelper(int[] num, int target, int start, int sum, 
　　　　　ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        if (sum > target) {
            return;
        }
        
        for (int i = start; i < num.length; i++) {
            if (i != start && num[i - 1] == num[i]) {
                continue;
            }
            if ((sum + num[i]) > target) {
                break;
            } 
            
            sum += num[i];
            curr.add(num[i]);
            
            combinationSumHelper(num, target, i + 1, sum, curr, result);
            
            sum -= num[i];
            curr.remove(curr.size() - 1);
        }
    }
}

Summary:
This question has a pitfall. For any permutation and combination problems in the code interview, you must first clarify with the interviewer that if the set contains duplicates. If yes, all duplicated numbers can be only traversed once.