Introduction
Backtracking 类型的题目最重要的是想清楚每一层在做什么,以及到下一层一共有几个分叉。
时间复杂度: branch factor ^ level
时间复杂度: call stack -> level
Subsets
这一类的题目的框架为,在递归树中的第 i 层,代表正在处理 nums 里的第 i 个元素。 从该层的父节点一定会伸展出两个分叉: 第一个分叉代表着一层会放这个元素,第二个分叉代表不放这个元素。 这样出来的递归树非常平衡。
Subsets I
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> rst;
sort(nums.begin(), nums.end());
vector<int> cur;
dfs(rst, cur, nums, 0);
return rst;
}
void dfs(vector<vector<int>> & rst, vector<int> & cur, const vector<int>& nums, int level) {
if (level == nums.size()) {
rst.emplace_back(cur);
return;
}
cur.emplace_back(nums[level]);
dfs(rst, cur, nums, level + 1);
cur.pop_back();
dfs(rst, cur, nums, level + 1);
}
};
Subsets II - Dedup
去重首先需要排序,要利用有序性。从递归树上看的话,放的那一个分支不变,因为我们是先做放元素,再走不放该元素的。如果不放该元素,那么此时的结果会跟父节点的是重复的。ab1 -> ab1b2, ab1。 a -> ab2, a。 ab1 和 ab2 不能同时出现。 所以这个分支就需要直接跳到跟当前层元素不同的那一层。在代码上体现就是level++。
ab1 ab2 出发产生的分支都是完全一样的。那么我们可以去掉ab2。
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> rst;
vector<int> cur;
sort(nums.begin(), nums.end());
dfs(rst, nums, 0, cur);
return rst;
}
void dfs(vector<vector<int>> & result, vector<int> & nums, int level, vector<int> & cur) {
if (level == nums.size()) {
result.emplace_back(cur);
return;
}
cur.emplace_back(nums[level]);
dfs(result, nums, level + 1, cur);
cur.pop_back();
//pruning techniques
while (level < nums.size() - 1 && nums[level] == nums[level+1]) {
level++;
}
dfs(result, nums, level + 1, cur);
}
};
Variant I - Combination
整体框架跟 Subset I 一模一样, 唯一的区别是 base case return 的时候加上条件: 当前结果的长度为 k 才返回。 原题链接:Combinations
去重的方法也应该和 Subset II 一样。
Variant II - Permutations of inserting spaces into a string
https://www.geeksforgeeks.org/print-possible-strings-can-made-placing-spaces/
Others
- 还有别的问法,比如如何分一个给定的数组成两部分,两部分的和相同。或者要在一串数组/字符串里面插入。
- 时间复杂度是$O(2^n)$
- 另一种常见做法:k层,每层的意义为最后的结果钟第几个元素应该是什么。
Permutations
因为全排列需要全部元素都出现,唯一不同的是他们的顺序,那么我们可以不停两两交换数组中的元素,得到全排列。
Time n * (n-1) * (n - 2) = O(n!)
Space O(n)
如果要求 一个长度不变的array/string 的 permutation 只是 order 不一样,就可以考虑用 swap-swap 的方法。
Permutations I
class Solution {
public:
vector<string> solve(string input) {
if (input == "") {
return {""};
}
vector<string> result;
helper(result, input, 0);
return result;
}
private:
void swap(string &s, int i, int j) {
auto temp = s[i];
s[i] = s[j];
s[j] = temp;
}
void helper(vector<string> & result, string & s, int index) {
if (index == s.size()){
result.emplace_back(s);
return;
}
for (int i = index; i < s.size(); i++) {
swap(s, i, index);
helper(result, s, index + 1);
swap(s, i, index);
}
}
};
Permutations II - Dedup
class Solution {
public:
vector<string> solve(string input) {
vector<string> result;
helper(input, result, 0);
return result;
}
private:
void helper(string & input, vector<string> & result, int level) {
if (level == input.size()) {
result.emplace_back(input);
return;
}
set<char> charset;
for (int i = level; i < input.size(); ++i) {
if (charset.find(input[i]) != charset.end()) {
continue;
}
charset.emplace(input[i]);
swap(input[i], input[level]);
helper(input, result, level + 1);
swap(input[i], input[level]);
}
}
};
Parenthesis Problems
Valid
Given N pairs of parentheses “()”, return a list with all the valid permutations.
分析:
void validParenthesisHelper(int l, int r, int n, string & cur, vector<string> & res) {
if (l + r == 2 * n) {
res.emplace_back(cur);
return;
}
if (l < n) {
cur += "(";
validParenthesisHelper(l + 1, r, n, cur, res);
cur.pop_back();
}
if (r < l) {
cur += ")";
validParenthesisHelper(l, r + 1, n, cur, res);
cur.pop_back();
}
}
vector<string> validParenthesis(int n) {
vector<string> res;
string cur;
validParenthesisHelper(0, 0, n, cur, res);
return res;
}
void testvalidParenthesis() {
auto res = validParenthesis(3);
for (const auto & str : res) {
cout << str << endl;
}
}
Time: O(2^2n) Space: O(2n)
Coin Combinations
99 Cents
https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/
void coinCombinationHelper(const vector<int> & coins,
vector<vector<int>> & res,
vector<int> & cur,
int remaining,
int level) {
if (level == coins.size()) {
if (remaining == 0) {
res.emplace_back(cur);
}
return;
}
int n = remaining/coins[level];
for (int i = 0; i <= n; i++) {
cur.emplace_back(i);
coinCombinationHelper(coins, res, cur, remaining - i * coins[level], level + 1);
cur.pop_back();
}
}
vector<vector<int>> coinCombination(const vector<int> & coins, int target) {
vector<vector<int>> res;
vector<int> cur;
coinCombinationHelper(coins, res, cur, target, 0);
return res;
}
void testCoinsCombination() {
vector<int> coins = {25, 10, 5, 1};
auto res = coinCombination(coins, 99);
for (const auto & v : res) {
for (const auto & c : v) {
cout << c << " ";
}
cout << endl;
}
}
find all valid combinations of factors that form an integer
https://www.geeksforgeeks.org/given-array-strings-find-strings-can-chained-form-circle/
Backtracking on Tree
Longest consecutive sequence
int global_max = INT_MIN;
int helper(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int left = 0;
int right = 0;
if (root->left && root->left->val -1 == root->val) {
left = helper(root->left);
}
if (root->right && root->right->val -1 == root->val) {
right = helper(root->right);
}
int local_max = max(left, right) + 1;
global_max = max(global_max, local_max)l
return local_max;
}