1 DFS 框架
result = []
void backtrack(路径,选择列表) {
if (满足条件) {
result.add(路劲);
return;
}
for 选择 in 选择列表
做选择
backtrack(路径,选择列表);
撤销选择
}
相关题目:
112 路径总和
class Solution {
public:
vector<int> path;
vector<int> res;
void dfs(TreeNode* root) {
if (root == nullptr) {
return;
}
if (root->left == nullptr && root->right == nullptr) {
res.push_back(accumulate(path.begin(), path.end(), root->val));
return;
}
path.push_back(root->val); //注意添加路径应放到return 后面,保证push / pop 是配对的
dfs(root->left);
dfs(root->right);
path.pop_back(); //删除vector 最后一个元素
}
bool hasPathSum(TreeNode* root, int targetSum) {
dfs(root);
for (auto item : res) {
if (item == targetSum) {
return true;
}
}
return false;
}
};
129 求根节点到叶子节点之和
class Solution {
StringBuilder path = new StringBuilder();
int res = 0;
public int sumNumbers(TreeNode root) {
// 遍历一遍二叉树就能出结果
traverse(root);
return res;
}
// 二叉树遍历函数
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序遍历位置,记录节点值
path.append(root.val);
if (root.left == null && root.right == null) {
// 到达叶子节点,累加路径和
res += Integer.parseInt(path.toString());
}
// 二叉树递归框架,遍历左右子树
traverse(root.left);
traverse(root.right);
// 后续遍历位置,撤销节点值
path.deleteCharAt(path.length() - 1);
}
}
46 全排列
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void dfs(vector<int>& nums, int n) { //n为已添加到path 的个数
if (n == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (count(path.begin(), path.end(), nums[i])) { //利用count 将重复数删除
continue;
}
path.push_back(nums[i]);
dfs(nums, n + 1);
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, 0);
return res;
}
};
回溯算法团灭子集/组合/排列问题
子集/组合/排列递归树
关键代码实现
子集/组合 用start控制重复数字的出现
for (int i = start; i < n; i++) {
.....
}
排列用count来控制重复数字出现
for (int i = 0; i < n; i++) {
if (count(begin(), end(), val)) {
continue;
}
......
}