回溯
回溯概念
题解
组合问题
LeetCode-77 组合
题目描述：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
题目思路：
代码
#include <iostream>
#include <vector>
#include <deque>
class Solution {
public:
std::vector<std::vector<int>> combine(int n, int k) {
std::vector<std::vector<int>> res;
if (k <= 0 || n < k) {
return res;
}
std::deque<int> path;
dfs(n, k, 1, path, res);
return res;
}
private:
void dfs(int n, int k, int begin, std::deque<int>& path, std::vector<std::vector<int>>& res) {
if (path.size() == k) {
res.push_back(std::vector<int>(path.begin(), path.end()));
return;
}
for (int i = begin; i <= n; i++) {
path.push_back(i);
printDeque(path, "递归之前 => ");
dfs(n, k, i + 1, path, res);
path.pop_back();
printDeque(path, "递归之后 => ");
}
}
void printDeque(const std::deque<int>& path, const std::string& prefix) {
std::cout << prefix;
for(const auto& num : path) {
std::cout << num << " ";
}
std::cout << std::endl;
}
};
int main() {
Solution solution;
int n = 4;
int k = 2;
std::vector<std::vector<int>> res = solution.combine(n, k);
for(const auto& list : res) {
std::cout << "[";
for(const auto& num : list) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
}
return 0;
}
before => 1
before => 1 2
after => 1
before => 1 3
after => 1
before => 1 4
after => 1
after =>
before => 2
before => 2 3
after => 2
before => 2 4
after => 2
after =>
before => 3
before => 3 4
after => 3
after =>
before => 4
after =>
[1 2 ]
[1 3 ]
[1 4 ]
[2 3 ]
[2 4 ]
[3 4 ]
LeetCode-216 组合Ⅲ
题目描述
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
- 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
题目思路
代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
dfs(k, n, 1);
return res;
}
private:
vector<vector<int>> res;
vector<int> path;
void dfs(int k, int n, int index);
static inline void printVector(const vector<int>& v, std::string prefix) {
cout << prefix;
for (const auto elem : v) {
cout << elem << " ";
}
cout << endl;
}
};
void Solution::dfs(int k, int n, int index) {
if (path.size() == k) {
if (accumulate(path.begin(), path.end(), 0) == n) res.push_back(path);
return;
}
for (int i = index; i <= 9; i++) {
printVector(path, "before");
path.push_back(i);
// if (path.size() > k) { // 无效剪枝
// path.pop_back();
// return;
// }
if (accumulate(path.begin(), path.end(), 0) > n) { // 剪枝
path.pop_back();
return;
}
dfs(k, n, i+1);
printVector(path, "after");
path.pop_back();
}
}
int main() {
Solution solution;
int k = 3, n = 7;
vector<vector<int>> v = solution.combinationSum3(k, n);
for(const auto& list : v) {
std::cout << "[";
for(const auto& num : list) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
}
return 0;
}
LeetCode-39 组合总数
题目描述：
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
解题思路
代码
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
back_tracking(candidates, target, 0);
return res;
}
private:
vector<vector<int>> res;
vector<int> path;
void back_tracking(vector<int>& candidates, int target, int index) {
if (accumulate(path.begin(), path.end(), 0) > target) {
return;
}
if (accumulate(path.begin(), path.end(), 0) == target) {
res.push_back(path);
return;
}
for (int i = index; i < candidates.size(); i++) {
path.push_back(candidates[i]);
back_tracking(candidates, target, i);
path.pop_back();
}
}
};
排列问题
LeetCode-46 全排列
题目描述
解题思路
代码
class Solution {
public:
/**
* 回溯算法相关知识点
* 回溯算法适用： 求解搜索问题和优化问题
* 搜索空间是树，结点对应部分解向量，可行解在叶结点上
* 搜索过程：采用系统的方法隐含的遍历搜索树
* 搜索策略： 深度优先， 宽度优先， 宽深结合， 函数优先
* 结点分支判定
* 结点状态
*/
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
dfs(nums, used);
return res;
}
private:
vector<vector<int>> res;
vector<int> path;
// 使用系统的方法隐含的遍历搜索树
void dfs(vector<int>& nums, vector<bool>& used) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == true) continue;
used[i] = true;
path.push_back(nums[i]);
dfs(nums, used);
path.pop_back();
used[i] = false;
}
}
};