[TOC]
第一题
解法一[暴力回溯法]
- 会超时
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
int sum = 0;
// 比较两个数组是否一样
bool issame_vector(vector<int> array1, vector<int> array2) {
sort(array1.begin(), array1.end());
sort(array2.begin(), array2.end());
if (array1.size() == array2.size()) {
int i;
for (i = 0; i < array1.size(); i++) {
if (array1[i] != array2[i]) break;
}
if (i == array1.size()) return true;
else return false;
}
else return false;
}
void backtracking(vector<int>& candidates, int target) {
if (sum > target) {
return;
}
else if (sum == target) {
// 判断是否有一样的数组，没有则加入
bool is_exist = false;
for (int i = 0; i < result.size(); i++) {
if (issame_vector(path, result[i])) is_exist = true;
}
if (!is_exist) result.push_back(path);
return;
}
else {
for (int i = 0; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target);
sum -= candidates[i];
path.pop_back();
}
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates, target);
return result;
}
};
解法二[回溯法]
- 空间复杂度O(n)
- 空间复杂度O(n)
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
int sum = 0;
// 加入开始下标，每种情况表示相当于固定不同的数字个数
void backtracking1(vector<int>& candidates, int target, int start) {
if (sum > target) {
return;
}
else if (sum == target) {
result.push_back(path);
return;
}
else {
for (int i = start; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking1(candidates, target, i);
sum -= candidates[i];
path.pop_back();
}
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking1(candidates, target, 0);
return result;
}
};
总结
- 这一题主要在于排除重复组合，我自己的方法排除重复组合过于暴力会超时。
- 加入开始下标这样可以避免重复的组合。
第二题
解法一[暴力排除重复组合法]
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
int sum = 0;
// 比较两个数组是否一样
bool issame_vector(vector<int> array1, vector<int> array2) {
sort(array1.begin(), array1.end());
sort(array2.begin(), array2.end());
if (array1.size() == array2.size()) {
int i;
for (i = 0; i < array1.size(); i++) {
if (array1[i] != array2[i]) break;
}
if (i == array1.size()) return true;
else return false;
}
else return false;
}
void backtracking(vector<int>& candidates, int target, int start) {
if (sum > target) return;
else if (sum == target) {
// 判断是否有一样的数组，没有则加入
bool is_exist = false;
for (int i = 0; i < result.size(); i++) {
if (issame_vector(path, result[i])) is_exist = true;
}
if (!is_exist) result.push_back(path);
return;
}
else {
for (int i = start; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, i + 1);
sum -= candidates[i];
path.pop_back();
}
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0);
return result;
}
};
解法二[正常回溯法]
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
int sum = 0;
void backtracking1(vector<int>& candidates, int target, int start) {
if (sum > target) return;
else if (sum == target) {
result.push_back(path);
}
else {
for (int i = start; i < candidates.size(); i++) {
// 要对同一树层使用过的元素进行跳过
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
sum += candidates[i];
path.push_back(candidates[i]);
backtracking1(candidates, target, i + 1);
sum -= candidates[i];
path.pop_back();
}
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// backtracking(candidates, target, 0);
sort(candidates.begin(), candidates.end());
backtracking1(candidates, target, 0);
return result;
}
};
总结
- 和第一题一样，暴力排除重复组合会超时。
- 先对数组排序，在回溯的过程中对同一树层已经使用过的元素进行排除，这里的同一树层指的是同一层的树的分支不出现相同的元素，但可以在同分支出现相同的元素。
第三题
解法一[回溯递归法]
- 时间复杂度O(n)
- 空间复杂度O(n)
class Solution {
private:
vector<vector<string>> result;
vector<string> path;
bool is_palindromic_string(string s) {
for (int i = 0; i < s.size() / 2; i++) {
if (s[i] != s[s.size() - i - 1]) return false;
}
return true;
}
// 回溯
void backtracking(string s, int start) {
// 结束当前切割方法
if (start == s.size()) {
bool is_path = true;
for (int i = 0; i < path.size(); i++) {
if (!is_palindromic_string(path[i])) is_path = false;
}
if (is_path) result.push_back(path);
return;
}
for (int i = start; i < s.size(); i++) {
string cur(s.begin() + start, s.begin() + i + 1);
path.push_back(cur);
backtracking(s, i + 1);
path.pop_back();
}
}
public:
vector<vector<string>> partition(string s) {
backtracking(s, 0);
return result;
}
};
解法二[优化的回溯递归法]
- 时间复杂度O(n)
- 空间复杂度O(n)
class Solution {
private:
vector<vector<string>> result;
vector<string> path;
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;
}
void backtracking2(string s, int start) {
if (start == s.size()) {
result.push_back(path);
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) {
string cur = s.substr(start, i - start + 1);
path.push_back(cur);
}
else continue;
backtracking2(s, i + 1);
path.pop_back();
}
}
public:
vector<vector<string>> partition(string s) {
// 方法二
backtracking2(s, 0);
return result;
}
};
总结
- 确实第一次见这种题，感觉主要在于如何将它与组合问题类比起来，关键在于如何切割字符串。
- 优化的方法主要在于判断回文字符串，第一种方式没有减枝，第二种方式进行了减枝。
- 对于动态规划来查询是否是回文字符串还需要学习一下。
总结
- 总体来说回溯法主要在于画出递归树，然后套上模板写好代码。
- 根据是否可以重复，start是否加1。
