39. 组合总和
思路
题目的关键点在于无限制重复选取，那么可以不用去重，只要和sum == target 就可以返回。
实现
点击查看代码
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backTracking(candidates, target, 0, 0);
return result;
}
vector<int> path;
vector<vector<int>> result;
void backTracking(vector<int>& candidates, int& target, int sum, int startIndex) {
if(sum == target) {
result.push_back(path);
return;
}
else if(sum > target) {
return;
}
for(int i = startIndex; i < candidates.size(); i++) {
path.push_back(candidates[i]);
backTracking(candidates, target, sum+candidates[i], i);
path.pop_back();
}
}
};
40. 组合总和 II
思路
这道题和上一题的区别在于数组中有重复数字且每个数字只能使用一次。因此，必须对数组进行排序，并对结果进行去重操作。
实现
点击查看代码
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
backTracking(candidates, target, 0, 0);
return result;
}
vector<int> path;
vector<vector<int>> result;
void backTracking(const vector<int>& candidates, const int& target, int sum, int startIndex) {
if(sum == target) {
result.push_back(path);
return;
}
for(int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
if(i > startIndex && candidates[i] == candidates[i-1]) continue;
path.push_back(candidates[i]);
backTracking(candidates, target, sum+candidates[i], i+1);
path.pop_back();
}
}
};
131.分割回文串
思路
1.先判断是不是回文串
2.如果是回文串，进入递归下一层
实现
点击查看代码
class Solution {
public:
vector<vector<string>> partition(string s) {
backTracking(s,0);
return result;
}
vector<string> path;
vector<vector<string>> result;
bool ispalindrome(string s) {
int left = 0;
int right = s.size()-1;
while(left <= right) {
if(s[left] != s[right]) return false;
left++;
right--;
}
return true;
}
void backTracking(const string& s, int startIndex) {
if(startIndex >= s.size()) {
result.push_back(path);
return;
}
for(int i = startIndex; i < s.size(); i++) {
if(s[i] != s[startIndex]) continue;
string a = s.substr(startIndex,i-startIndex+1);
if(!ispalindrome(a)) continue;
path.push_back(a);
backTracking(s,i+1);
path.pop_back();
}
}
};