Leetcode40 无重复组合之和

题目描述：

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

思路分析

这个题是leetcode39的延续组合之和
若不考虑重复，一个简单的思路是递归+回溯，要考虑去重, 一种有效做法是先排序，相同元素在同一条递归路径下只被选取一次，这样可以实现有效剪枝

代码实现

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
 List<List<Integer>> bs=new ArrayList<List<Integer>>(); 
	List<Integer> bp = new ArrayList<Integer>();
	Arrays.sort(candidates);
	dfs(bs,bp,0,target,candidates);//深度优先搜索
	return bs;
	}

//Leetcode高票答案
	private static void dfs(List<List<Integer>> result, List<Integer> temp, int index, int target, int[] coins){
        //termination condition;
        if(target < 0){
            return ;    
        }
        
        if(target == 0){
            result.add(new ArrayList<>(temp));
            return;
        }
        
        for(int i = index; i < coins.length && target >= coins[i]; i++){
            //when i is bigger than index & still duplicates(位置i处元素值之前加入过) we continue;
            if(i > index && coins[i] == coins[i-1]){
                continue;    
            }//有效避免重复 a a .. 与 a .. 情况重复出现(a代表当前要添加的元素)
            temp.add(coins[i]);
            dfs(result, temp, i + 1, target - coins[i], coins); // we cannot reuse it;
            temp.remove(temp.size()-1);
        }        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32