?
??題目：
39. 組合總和
給你一個?無重復(fù)元素?的整數(shù)數(shù)組?candidates?和一個目標(biāo)整數(shù)?target?，找出?candidates?中可以使數(shù)字和為目標(biāo)數(shù)?target?的 所有?不同組合?，并以列表形式返回。你可以按?任意順序?返回這些組合。
candidates?中的?同一個?數(shù)字可以?無限制重復(fù)被選取?。如果至少一個數(shù)字的被選數(shù)量不同，則兩種組合是不同的。?
對于給定的輸入，保證和為?target?的不同組合數(shù)少于?150?個。
示例?1：
輸入：candidates =[2,3,6,7],target =7輸出：[[2,2,3],[7]] 解釋： 2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一個候選， 7 = 7 。 僅有這兩種組合。
示例?2：
輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
輸入: candidates = [2], target = 1
輸出: []
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40-
candidates?的所有元素?互不相同 1 <= target <= 40
思考?xì)v程與知識點(diǎn)：?
題目中的無限制重復(fù)被選取，嚇得我趕緊想想 出現(xiàn)0 可咋辦，然后看到下面提示：1 <= candidates[i] <= 200，我就放心了。
本題和77.組合? 、216.組合總和III?的區(qū)別是：本題沒有數(shù)量要求，可以無限重復(fù)，但是有總和的限制，所以間接的也是有個數(shù)的限制。
單層for循環(huán)依然是從startIndex開始，搜索candidates集合。
?題解：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum, i); // 不用i+1了，表示可以重復(fù)讀取當(dāng)前的數(shù)
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
backtracking(candidates, target, 0, 0);
return result;
}
};??題目：
40. 組合總和 II
給定一個候選人編號的集合?candidates?和一個目標(biāo)數(shù)?target?，找出?candidates?中所有可以使數(shù)字和為?target?的組合。
candidates?中的每個數(shù)字在每個組合中只能使用?一次?。
注意：解集不能包含重復(fù)的組合。?
示例?1:
輸入: candidates =?[10,1,2,7,6,1,5], target =?8, 輸出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例?2:
輸入: candidates =?[2,5,2,1,2], target =?5, 輸出: [ [1,2,2], [5] ]
提示:
1 <=?candidates.length <= 1001 <=?candidates[i] <= 501 <= target <= 30
思考?xì)v程與知識點(diǎn)：?
如果candidates[i] == candidates[i - 1]?并且?used[i - 1] == false，就說明：前一個樹枝，使用了candidates[i - 1]，也就是說同一樹層使用過candidates[i - 1]。
此時for循環(huán)里就應(yīng)該做continue的操作。
?題解：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
// used[i - 1] == true，說明同一樹枝candidates[i - 1]使用過
// used[i - 1] == false，說明同一樹層candidates[i - 1]使用過
// 要對同一樹層使用過的元素進(jìn)行跳過
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i + 1, used); // 和39.組合總和的區(qū)別1，這里是i+1，每個數(shù)字在每個組合中只能使用一次
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<bool> used(candidates.size(), false);
path.clear();
result.clear();
// 首先把給candidates排序，讓其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
};??題目：
131. 分割回文串
給你一個字符串?s，請你將?s?分割成一些子串，使每個子串都是?回文串?。返回?s?所有可能的分割方案。
回文串?是正著讀和反著讀都一樣的字符串。
示例 1：
輸入：s = "aab" 輸出：[["a","a","b"],["aa","b"]]
示例 2：
輸入：s = "a" 輸出：[["a"]]
提示：
1 <= s.length <= 16-
s?僅由小寫英文字母組成
思考?xì)v程與知識點(diǎn)：?
本題這涉及到兩個關(guān)鍵問題：
- 切割問題，有不同的切割方式
- 判斷回文
全局變量數(shù)組path存放切割后回文的子串，二維數(shù)組result存放結(jié)果集。 （這兩個參數(shù)可以放到函數(shù)參數(shù)里）
本題遞歸函數(shù)參數(shù)還需要startIndex，因?yàn)榍懈钸^的地方，不能重復(fù)切割，和組合問題也是保持一致的。
?題解：
class Solution {
private:
vector<vector<string>> result;
vector<string> path; // 放已經(jīng)回文的子串
void backtracking (const string& s, int startIndex) {
// 如果起始位置已經(jīng)大于s的大小，說明已經(jīng)找到了一組分割方案了
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome(s, startIndex, i)) { // 是回文子串
// 獲取[startIndex,i]在s中的子串
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else { // 不是回文，跳過
continue;
}
backtracking(s, i + 1); // 尋找i+1為起始位置的子串
path.pop_back(); // 回溯過程，彈出本次已經(jīng)填在的子串
}
}
bool isPalindrome(const string& s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};歡迎點(diǎn)贊，收藏，評論，你的鼓勵就是我創(chuàng)作的最大動力！(????)?"""文章來源：http://www.zghlxwxcb.cn/news/detail-502119.html
版權(quán)聲明：本文為CSDN博主「渡夢酒」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：渡夢酒的博客_CSDN博客-csdn領(lǐng)域博主文章來源地址http://www.zghlxwxcb.cn/news/detail-502119.html
到了這里，關(guān)于【Leetcode60天帶刷】day27回溯算法——39. 組合總和，40.組合總和II，131.分割回文串的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
