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.

Have you met this question in a real interview?

Yes

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]
]

this problem is to remove the dups in the data set, the method used here is to select one ordered series as our representative and remove everything else.

i.e. 1, 2, 2, in the case where the first 2 is skipped and the second 2 is added, we will disallow this to remove duplicates list.

at that time i > startIndex, (startIndex was at 0) and num[i - 1] == num[i] , but we need to allow if they are selected in order i == startIndex and num[i-1] == num[i]

public class Solution {
    /**
     * @param num: Given the candidate numbers
     * @param target: Given the target number
     * @return: All the combinations that sum to target
     */
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        // write your code here
        List<List<Integer>> ans = new ArrayList<>();
        if (num == null || num.length == 0) {
            return ans;
        }

        Arrays.sort(num);

        List<Integer> cur = new ArrayList<>();
        dfsCombinationSum2(ans, cur, num, target, 0);

        return ans;
    }

    public void dfsCombinationSum2(List<List<Integer>> ans,
                                   List<Integer> cur,
                                   int[] num,
                                   int target,
                                   int startIndex) {
        if (target < 0) {
            return;
        }

        if (target == 0) {
            ans.add(new ArrayList<Integer>(cur));
            return;
        }

        for (int i = startIndex; i < num.length; i++) {
            if ((i - 1) >= 0 && i != startIndex && num[i - 1] == num[i]) {
                continue;
            }
            cur.add(num[i]);
            dfsCombinationSum2(ans, cur, num, target - num[i], i + 1);
            cur.remove(cur.size() - 1);
        }
    }

}