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);}        }
}