39.?組合總和
思路：
這道題的思路與之前題目思路相似页滚，只不過(guò)candidate里面的數(shù)可以重復(fù)使用召边，所以在進(jìn)行遞歸操作的時(shí)候傳入的參數(shù)需要留意。
代碼：
class Solution {
public:
? ? vector<int> path;
? ? vector<vector<int>> res;
? ? void backtracking(vector<int>& candidates, int target,int sum,int index)
? ? {
? ? ? ? if(sum>target)return;
? ? ? ? if(sum==target)
? ? ? ? {
? ? ? ? ? ? res.push_back(path);
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? for(int i=index;i<candidates.size();i++)
? ? ? ? {
? ? ? ? ? ? path.push_back(candidates[i]);
? ? ? ? ? ? sum+=candidates[i];
? ? ? ? ? ? backtracking(candidates,target,sum,i);
? ? ? ? ? ? sum-=candidates[i];
? ? ? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
? ? ? ? backtracking(candidates,target,0,0);
? ? ? ? return res;
? ? }
};
40.?組合總和 II
思路：
這道題的難點(diǎn)在于原本的candidate數(shù)組中含有重復(fù)的元素裹驰，但是輸出的結(jié)果在組合邏輯上不能重復(fù)隧熙，這就要求做去重處理，在對(duì)原來(lái)數(shù)組經(jīng)過(guò)排序后幻林，相同的元素在相鄰的位置贱鼻，在元素遍歷的過(guò)程中就只需要使用第一個(gè)元素，后面的元素直接跳過(guò)即可滋将，這樣的邏輯可以用一個(gè)與原數(shù)組相同大小的標(biāo)志數(shù)組used表示邻悬，如果相同的幾個(gè)元素中最開(kāi)始的元素uesd標(biāo)志位為1，則表示首位已經(jīng)搜索随闽，后面的無(wú)需再搜索父丰，直接跳過(guò)即可。
代碼：
class Solution {
public:
? ? vector<int> path;
? ? vector<vector<int>> res;
? ? void backtracking(vector<int>& candidates, int target,int sum,int index,vector<bool> used)
? ? {
? ? ? ? if(sum>target) return;
? ? ? ? if(sum==target)
? ? ? ? {
? ? ? ? ? ? res.push_back(path);
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? for(int i=index;i<candidates.size();i++)
? ? ? ? {
? ? ? ? ? ? if(i>0 && used[i-1]==false && candidates[i]==candidates[i-1]) continue;
? ? ? ? ? ? path.push_back(candidates[i]);
? ? ? ? ? ? used[i]=true;
? ? ? ? ? ? sum+=candidates[i];
? ? ? ? ? ? backtracking(candidates,target,sum,i+1,used);
? ? ? ? ? ? sum-=candidates[i];
? ? ? ? ? ? used[i]=false;
? ? ? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
? ? ? ? vector<bool> used(candidates.size(),false);
? ? ? ? sort(candidates.begin(),candidates.end());
? ? ? ? backtracking(candidates,target,0,0,used);
? ? ? ? return res;
? ? }
};
131.?分割回文串
代碼：
class Solution {
public:
? ? vector<string> path;
? ? vector<vector<string>> res;
? ? void backtracking(const string& s,int index)
? ? {
? ? ? ? if(index>=s.size())
? ? ? ? {
? ? ? ? ? ? res.push_back(path);
? ? ? ? ? ? return;
? ? ? ? }
? ? for (int i = index; i < s.size(); i++) {
? ? ? ? if (isPalindrome(s, index, i)) {?
? ? ? ? ? ? string str = s.substr(index, i - index + 1);
? ? ? ? ? ? path.push_back(str);
? ? ? ? } else {? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? backtracking(s, i + 1);
? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? 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;
? ? }
? ? vector<vector<string>> partition(string s) {
? ? ? ? backtracking(s, 0);
? ? ? ? return res;
? ? }
};
