回溯法分类(backtack)
- 组合问题
- 分割问题
- 子集问题
- 排序问题
- 棋盘问题
- 其他
关于回溯算法，你该了解这些！
组合问题
77. 组合
class Solution {
public:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件的结果
vector<vector<int>> combine(int n, int k) {
backtrace(n, k, 1);
return result;
}
void backtrace(int n, int k, int startIndex) {
if (path.size() == k) {
result.emplace_back(path);
return;
}
for (int i = startIndex; i <= n - (k - path.size()) + 1; ++i) { // 控制树的横向遍历
path.emplace_back(i);
backtrace(n, k, i + 1);
path.pop_back();
}
}
};216. 组合总和 III
class Solution {
public:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件的结果
int target;
const int nums = 9;
vector<vector<int>> combinationSum3(int k, int n) {
target = n;
backtrace(k, 1);
return result;
}
void backtrace(int k, int startIndex) {
if (path.size() == k) {
if (accumulate(path.begin(), path.end(), 0) == target) {
result.emplace_back(path);
}
return;
}
for (int i = startIndex; i <= nums - (k - path.size()) + 1; ++i) { // 控制树的横向遍历
path.emplace_back(i);
backtrace(k, i + 1);
path.pop_back();
}
}
};17. 电话号码的字母组合
class Solution {
public:
vector<string> result; // 存放符合条件结果的集合
string path; // 用来存放符合条件的结果
map<char, string> numStr = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
string s;
vector<string> letterCombinations(string digits) {
if (!digits.size()) return result;
backtrace(digits, 0);
return result;
}
void backtrace(string &digits, int idx) {
if (idx == digits.size()) {
result.emplace_back(path);
return;
}
for (int i = 0; i < numStr[digits[idx]].size(); ++i) { // 控制树的横向遍历
path.push_back(numStr[digits[idx]][i]);
backtrace(digits, idx + 1); // 问题所在，是idx而非i
path.pop_back();
}
}
};39. 组合总和
class Solution {
public:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件的结果
int curr = 0; // 记录path当前和
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtrace(candidates, target, 0);
return result;
}
void backtrace(vector<int>& candidates, int target, int idx) {
if (curr > target) {
return;
}
if (curr == target) {
result.emplace_back(path);
return;
}
for (int i = idx; i < candidates.size(); ++i) { // 控制树的横向遍历
if (curr + candidates[i] <= target) {
path.emplace_back(candidates[i]);
curr += candidates[i];
backtrace(candidates, target, i); // // 不用i+1了，表示可以重复读取当前的数 ===== 理解这个地方放idx和i的区别
curr -= candidates[i];
path.pop_back();
}
}
}
};40. 组合总和 II
class Solution {
public:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件的结果
int curr = 0; // 记录path当前和
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end()); // 需要注意的是去重需要排序
backtrace(candidates, target, 0);
return result;
}
void backtrace(vector<int>& candidates, int target, int idx) {
if (curr == target) {
result.emplace_back(path);
return;
}
for (int i = idx; i < candidates.size() && curr + candidates[i] <= target; ++i) { // 控制树的横向遍历
if (i > idx && candidates[i] == candidates[i - 1]) { // 如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。
continue;
}
path.emplace_back(candidates[i]);
curr += candidates[i];
backtrace(candidates, target, i + 1); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
curr -= candidates[i];
path.pop_back();
}
}
};分割问题
切割问题其实是一种组合问题！
131. 分割回文串
class Solution {
public:
vector<vector<string>> result; // 存放符合条件结果的集合
vector<string> path; // 用来存放符合条件的结果
int n;
vector<vector<string>> partition(string s) {
n = s.size();
vector<vector<bool>> judge(n, vector<bool>(n, false)); // 判断是否为回文子串
fullPalindrome(s, judge); // 填充回文子串
backtrace(s, 0, judge);
return result;
}
void backtrace(string &s, int idx, vector<vector<bool>> judge) {
if (idx == n) {
result.push_back(path);
return;
}
for (int i = idx; i < n; ++i) { // 控制树的横向遍历
if (judge[idx][i]) { // 判断是否为回文子串
// 获取[idx,i]在s中的子串
string str = s.substr(idx, i - idx + 1);
path.emplace_back(str);
} else { // 如果不是直接跳过
continue;
}
backtrace(s, i + 1, judge); // 寻找i+1为起始位置的子串
path.pop_back();
}
}
void fullPalindrome(string &s, vector<vector<bool>> &judge) {
// 初始化
for (int i = s.size() - 1; i >= 0; i--) { // 借鉴别人写的，自己还不是很熟
// 需要倒序计算, 保证在i行时, i+1行已经计算好了
for (int j = i; j < s.size(); j++) {
if (j == i) {judge[i][j] = true;}
else if (j - i == 1) {judge[i][j] = (s[i] == s[j]);}
else {judge[i][j] = (s[i] == s[j] && judge[i+1][j-1]);}
}
}
}
};93. 复原 IP 地址
class Solution {
public:
vector<string> result; // 存放符合条件结果的集合
const int pointCnt = 3;
vector<string> restoreIpAddresses(string s) {
backtrace(s, 0, 0);
return result;
}
void backtrace(string &s, int idx, int num) {
if (num == pointCnt) {
if (isValid(s, idx, s.size() - 1)) {
// 判断最后一段数字是否有效
result.push_back(s);
}
return;
}
for (int i = idx; i < s.size(); ++i) { // 控制树的横向遍历
if (i - idx < 3 && isValid(s, idx, i)) { // 判断是否为有效分割
// 获取[idx,i]在s中的子串
s.insert(s.begin() + i + 1, '.'); // 在i后面插一个.号
num++;
backtrace(s, i + 2, num); // 插入逗号后之后的下一个子串的起始位置为i+2
num--;
s.erase(s.begin() + i + 1); // 回溯删除逗号
} else { // 如果不是直接跳过
break; // 以下更不符合
}
}
}
bool isValid(const string &s, int start, int end) { // 判断是否分割有效
// 判断条件:
if (start > end) {
return false;
}
if (s[start] == '0' && start != end) { // 前导0，原来这么简单判断即可
return false;
}
int num = 0; // 统计数字的大小
for (int i = start; i <= end; ++i) {
int temp = s[i] - '0'; // 将字符转换为数字
num = num * 10 + temp; // 注意此处不能缩写*=，会出错
if (num > 255) { // 判断范围在0到255之间
return false;
}
}
return true;
}
};子集问题
78. 子集
class Solution {
public:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件的结果
int n;
vector<vector<int>> subsets(vector<int>& nums) {
n = nums.size();
backtrace(nums, 0);
return result;
}
void backtrace(vector<int>& nums, int idx) {
result.emplace_back(path);
if (path.size() == n) {
return;
}
for (int i = idx; i < n; ++i) { // 控制树的横向遍历
path.emplace_back(nums[i]);
backtrace(nums, i + 1);
path.pop_back();
}
}
};90. 子集 II
class Solution {
public:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件的结果
int n;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
n = nums.size();
sort(nums.begin(), nums.end());
backtrace(nums, 0);
return result;
}
void backtrace(vector<int>& nums, int idx) {
result.emplace_back(path);
if (path.size() == n) {
return;
}
for (int i = idx; i < n; ++i) { // 控制树的横向遍历
if (i > idx && nums[i] == nums[i - 1]) { // 好叭，我承认我是死记硬背的
continue;
}
path.emplace_back(nums[i]);
backtrace(nums, i + 1);
path.pop_back();
}
}
};排列问题
46. 全排列
class Solution {
public:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件的结果
int n;
vector<vector<int>> permute(vector<int>& nums) {
n = nums.size();
vector<int> used(n);
backtrace(nums, used);
return result;
}
void backtrace(const vector<int>& nums, vector<int>& used) {
if (path.size() == n) {
result.emplace_back(path);
return;
}
for (int i = 0; i < n; ++i) { // 控制树的横向遍历
if (!used[i]) { // 没有被访问
used[i] = 1;
path.emplace_back(nums[i]);
backtrace(nums, used);
path.pop_back();
used[i] = 0;
}
}
}
};47. 全排列 II
class Solution {
public:
vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件的结果
int n;
vector<vector<int>> permuteUnique(vector<int>& nums) {
n = nums.size();
sort(nums.begin(), nums.end()); // 去重步骤1
vector<int> used(n);
backtrace(nums, used);
return result;
}
void backtrace(const vector<int>& nums, vector<int>& used) {
if (path.size() == n) {
result.emplace_back(path);
return;
}
for (int i = 0; i < n; ++i) { // 控制树的横向遍历
// 去重步骤2
if (i > 0 && nums[i-1] == nums[i] && !used[i-1]) {
continue;
}
if (!used[i]) { // 没有被访问
used[i] = 1;
path.emplace_back(nums[i]);
backtrace(nums, used);
path.pop_back();
used[i] = 0;
}
}
}
};棋盘问题
51. N 皇后
37. 解数独
其他
491. 递增子序列
332. 重新安排行程
总结