給定一組不同的整數候選者和一個目標整數目標，傳回所有唯一的候選者組合的列表，其中所選數字總和達到目標。您可以按任何順序返回組合。
相同的號碼可以從候選人中無限次地選擇。兩個組合是唯一的，如果
頻率
至少有一個所選數字不同。
產生的測試案例使得對於給定輸入而言，總和達到目標的唯一組合數量少於 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 = "aab"
輸出：[["a","a","b"],["aa","b"]]
範例2：
輸出：[[“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中文網其他相關文章！
