40.组合总和II-创新互联
40. 组合总和 II
分享文章:40.组合总和II-创新互联
标题路径:http://pwwzsj.com/article/hjspi.html
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
成都创新互联公司成立与2013年,先为赤城等服务建站,赤城等地企业,进行企业商务咨询服务。为赤城企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:示例 2:输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
提示:输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
1<= candidates.length<= 100
1<= candidates[i]<= 50
1<= target<= 30
回溯:(见:39. 组合总和)
重点在于去重:(具体原理见:47. 全排列 II)
if(i >0 && candidates[i - 1] == candidates[i] && hasVisited[i - 1] == false) {
continue;
}
代码:(Java)import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class combinationSumII {public static void main(String[] args) {// TODO Auto-generated method stub
int [] candidates = {10,1,2,7,6,1,5};
int target = 8;
System.out.println(combinationSum2(candidates, target));
}
public static List>combinationSum2(int[] candidates, int target) {List>combinations = new ArrayList<>();
Listcombination = new ArrayList<>();
Arrays.sort(candidates);
boolean [] hasVisited = new boolean[candidates.length];
if(candidates == null || candidates.length == 0){ return combinations;
}
backtracking(combinations, combination, candidates, 0 ,target, hasVisited);
return combinations;
}
private static void backtracking(List>combinations, Listcombination, int[] candidates,
int start, int target, boolean[] hasVisited) {// TODO Auto-generated method stub
if(target == 0) { combinations.add(new ArrayList<>(combination));
return;
}
int end = search(candidates, target);
if(end< start || target< candidates[start]){ return;
}
for(int i = start; i<= end; i++){ if(i >0 && candidates[i - 1] == candidates[i] && hasVisited[i - 1] == false) { continue;
}
hasVisited[i] = true;
combination.add(candidates[i]);
backtracking(combinations, combination, candidates, i + 1, target - candidates[i], hasVisited);
combination.remove(combination.size() - 1);//回溯
hasVisited[i] = false;
}
}
private static int search(int[] candidates, int target) {//二分查找
// TODO Auto-generated method stub
if(target< candidates[0]){ return -1;
}
int r = candidates.length - 1;
int l = 0;
while(l< r) { int mid = l + (r - l) / 2;
if(candidates[mid] >target) { r = mid - 1;
}else if(r == l + 1) { break;
}else{ l = mid;
}
}
if(candidates[r] >target) { r = l;
}
return r;
}
}
运行结果:注:仅供学习参考!来源:力扣.
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
分享文章:40.组合总和II-创新互联
标题路径:http://pwwzsj.com/article/hjspi.html