Combination Sum II

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

Each number in Cmay 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 target 8,

A solution set is:

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

这道题尝试用一个visited[] 数组存放排序的情况，结果超时了。这道题先对数组进行排序，应该用一个pre变量就好，如果当前元素跟前一个元素相同，那么不去遍历它，因为同一层的话会重复计算。比如说数组为

[1,1,2,3], k = 2 target = 3

那么在遍历的时候，1先被加进去，然后会dfs计算出结果：[1, 2]，然后返回到跟index=0的1的相同层。 这时记录pre的值为1( index = 0)，  这时发现index=1的值跟pre相等，于是跳过1，到2（index = 2），然后计算出结果[]。一次类推，到3，返回结果[]。

代码：

public List<List<Integer>> combinationSum2(int[] num, int target) { // write your code here List<List<Integer>> result = new ArrayList<>(); if(num == null || num.length == 0) return result; Arrays.sort(num); //boolean[] visited = new boolean[num.length]; List<Integer> list = new ArrayList<>(); dfs(result, list, 0, target, num); return result; } private void dfs(List<List<Integer>> result, List<Integer> list, int index, int target, int[] num){ if(target == 0){ result.add(new ArrayList<Integer>(list)); return; } int pre = -1; for(int i=index;i<num.length;i++){ if(target<num[i]) return; if(pre == num[i]) continue; pre = num[i]; list.add(num[i]); dfs(result, list, i+1, target - num[i], num); list.remove(list.size()-1); } }