做数学ppt工具的网站,酒泉网站建设推广,wordpress 优惠券插件,快速网页制作工具题目描述#xff1a;
给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意#xff1a;解集不能包含重复的组合。
思路分析
这个题是…题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意解集不能包含重复的组合。
思路分析
这个题是leetcode39的延续组合之和 若不考虑重复一个简单的思路是递归回溯要考虑去重, 一种有效做法是先排序相同元素在同一条递归路径下只被选取一次这样可以实现有效剪枝
代码实现
class Solution {public ListListInteger combinationSum2(int[] candidates, int target) {ListListInteger bsnew ArrayListListInteger(); ListInteger bp new ArrayListInteger();Arrays.sort(candidates);dfs(bs,bp,0,target,candidates);//深度优先搜索return bs;}//Leetcode高票答案private static void dfs(ListListInteger result, ListInteger 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);} }
}
