1.回溯法的主体结构
- 回溯出口，当找到了一个问题的解时，存储该解。
- 回溯主体，遍历当前状态的所有子节点(通常使用一个for循环)，并判断下一个状态是否满足问题条件，如满足，则进入下一个状态。
- 状态返回，如果当前状态不满足solution条件，便返回到前一个状态。
2. Examples
2.1 subsets
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
代码：
class Solution {
private:
void backtrack(vector<vector<int>>& res, vector<int>&temp, vector<int>&nums, int start){
res.push_back(temp);
for(int i = start; i < nums.size(); i++){
temp.push_back(nums[i]);
backtrack(res, temp, nums, i+1);
temp.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
backtrack(res, temp, nums, 0);
return res;
}
};
2.2 Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:
Input: candidates = [2], target = 1
Output: []
代码：
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> res;
vector<int> temp;
backtrack(res, temp, candidates, target, 0);
return res;
}
void backtrack(vector<vector<int>>& res, vector<int>& temp, vector<int>& candidates, int target, int index){
if(target<0) return;
if(target==0){
res.push_back(temp);
return;
}
for(int i = index; i < candidates.size(); i++){
temp.push_back(candidates[i]);
backtrack(res, temp, candidates, target-candidates[i], i);
temp.pop_back();
}
}
};
2.3 Subsets II
这道题还是困扰了我一会的，与之前的SubSets相比，此题的变化就是所给的nums里面是有重复元素的。整个回溯过程与之前相比是几乎相同，除了路径选择这一块Subset II需要多加一步判断：
- 该数不是在本次搜索深度中选择列表里的第一个
- 该数与选择列表中上一个数相同
若上述两个条件同时满足，那就跳过i，进入到i+1
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
vector<int> temp;
backtrack(res, nums, temp, 0);
return res;
}
void backtrack(vector<vector<int>>& res, vector<int>& nums, vector<int>& temp, int index){
res.push_back(temp);
for(int i = index; i < nums.size(); i++){
if(i != index && nums[i]==nums[i-1])
continue;
temp.push_back(nums[i]);
backtrack(res, nums, temp, i+1);
temp.pop_back();
}
}
};
2.4 Generate Parentheses
本题告诉了我回溯法不是只有一个僵硬的for循环+递归的框架，有时需要引入其他变量灵活变通，当然这种能力还需要训练...
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
string tmp;
int open = 0, close = 0;
backtrack(res, tmp, open, close, n);
return res;
}
void backtrack(vector<string>& res, string& tmp, int open, int close, int n){
if(tmp.size()==2*n){
res.push_back(tmp);
return;
}
if(open < n){
tmp.push_back('(');
backtrack(res, tmp, open+1, close, n);
tmp.pop_back();
}
if(close < open){
tmp.push_back(')');
backtrack(res, tmp, open, close+1, n);
tmp.pop_back();
}
}
};
接下来要找个机会挑战下8皇后了
