给定一组不同的整数候选者和一个目标整数目标，返回所有唯一的候选者组合的列表，其中所选数字之和达到目标。您可以按任何顺序返回组合。
相同的号码可以从候选人中无限次地选择。两个组合是唯一的，如果
频率
至少有一个所选数字不同。
生成的测试用例使得对于给定输入而言，总和达到目标的唯一组合数量少于 150 个组合。
示例1：
输入：候选人= [2,3,6,7]，目标= 7
输出：[[2,2,3],[7]]
说明：
2 和 3 是候选数，2 + 2 + 3 = 7。请注意，2 可以多次使用。
7 是候选者，7 = 7。
这是仅有的两种组合。
示例2：
输入：候选人= [2,3,5]，目标= 8
输出：[[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入：候选人 = [2]，目标 = 1
输出：[]
限制：
1
2
候选人的所有元素都是独特的。
1
原始页面
这道题和昨天解决的题差别不是很大。
BackTracking 仍然可以很好地搜索深度的可能性并使用循环进行宽度控制。
需要注意的是，这里我们可以添加相同的元素，然后保持整个组合的唯一性。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<>();
List<Integer> combs = new LinkedList<>();
backTracking(list, combs, candidates, target, 0, 0);
return list;
}
public void backTracking(List<List<Integer>>list, List<Integer> combs, int[] candidates, int target, int sum, int start){
if(sum > target){
return;
}
if(sum == target){
list.add(new ArrayList<>(combs));
return;
}
for(int i=start; i<candidates.length; i++){
combs.add(candidates[i]);
sum += candidates[i];
backTracking(list, combs, candidates, target, sum, i);
combs.remove(combs.size()-1);
sum -= candidates[i];
}
Set<List<Integer>> set = new HashSet<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<Integer> combs = new LinkedList<>();
Arrays.sort(candidates);
backTracking(combs, target, candidates, 0, 0);
return new ArrayList<>(set);
}
public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum){
if(sum > target){
return;
}
if(sum == target){
set.add(new ArrayList<>(combs));
}
for(int i=start; i<candidates.length; i++){
if(candidates[i] + sum > target){
continue;
}
sum += candidates[i];
combs.add(candidates[i]);
backTracking(combs, target, candidates, i+1, sum);
sum -= candidates[i];
combs.remove(combs.size()-1);
}
}
因为有一些元素之前已经使用过，例如[1,1,1,2,3] 第一次递归中使用了112，但是循环会遍历从1到3开始的所有元素，并且存在三个“1”，所以当遇到第二个“1”时，组合112也会找到，这个在前面的递归步骤中已经找到了，所以我们应该把这些多余的步骤减少（同样的，在递归的遍历和递归的横向递归中也可能发生这种情况。
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<Integer> combs = new LinkedList<>();
Arrays.sort(candidates);
backTracking(combs, target, candidates, 0, 0, false);
return list;
}
public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum, boolean horizon){
if(sum > target){
return;
}
if(sum == target){
list.add(new ArrayList<>(combs));
}
for(int i=start; i<candidates.length; i++){
if(candidates[i] + sum > target){
continue;
}
if(i!=0 && candidates[i] == candidates[i-1] && horizon){
continue;
}
sum += candidates[i];
combs.add(candidates[i]);
backTracking(combs, target, candidates, i+1, sum, false);
sum -= candidates[i];
combs.remove(combs.size()-1);
horizon = true;
}
}
给定一个字符串 s，对 s 进行分区，使得每个
子串
分区的 是
回文
。返回 s 所有可能的回文划分。
示例1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例2：
输入：s = "a"
输出：[["a"]]
限制：
1
s 仅包含小写英文字母。
原始页面
List<List<String>> list = new ArrayList<>();
public List<List<String>> partition(String s) {
List<String> combs = new ArrayList<>();
backTracking(combs, new StringBuilder(s), 0);
return list;
}
public void backTracking(List<String> combs, StringBuilder str, int start){
if(start == str.length()){
list.add(new ArrayList<>(combs));
return;
}
for(int i=1; i+start <= str.length(); i++){
String cur = str.substring(start, start+i);
if(!isParlindrome(cur)){
continue;
}
combs.add(cur);
backTracking(combs, str, start+i);
combs.remove(combs.size()-1);
}
}
public boolean isParlindrome(String s){
int left = 0;
int right = s.length()-1;
while(left<right){
if(s.charAt(left++)!=s.charAt(right--)){
return false;
}
}
return true;
}
以上是LeetCode DayBackTracking 第 2 部分的详细内容。更多信息请关注PHP中文网其他相关文章！
