1. 算法讲解
回溯法（backtracking）本质其实是一种在深度优先搜索（DFS）的基础上，加入了剪枝函数（pruning），从而使得空间复杂度在一定程度上有所降低。回溯法适合组合数相当大的问题，也就是许多组合优化的问题适合用回溯法解决。
常见的地方有两个
backtrack函数的开头，剪掉后方便放入收集容器- for循环的开头，一般是去重
回溯函数的一般化流程是:
void backtrack(原数组，结果容器，临时容器，起始位置，....)
{
if(...) return//剪枝条件
if(...) //结果容器收集条件
{
res.push_back(tmp);
return;
}
//回溯过程
for(int i=start;i<nums.size();i++)
{
//这里也可能有剪枝条件，比如去除重复元素
tmp.push_back();
backtrack(位置);
tmp.pop_back();
}
}
2. 组合问题
组合是按先后顺序依次进行，区分组合和排列的关键就是看：前面用过后面还用不用。
比如，[1,2,3]的全排列，1虽然用过，但依然可能出现在其他位置，再接着用；而[1,2,3,4,5]数组中和为8的数组集合，这里用过1（pass过）就不会再出现了。所以排列问题需要用flag标记，组合则不需要。
039 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
解答：
注意，要排序！最后调用backtrack进入的是i，不是start！并且不加1（candidates 中的数字可以无限制重复被选取）。注意要传引用。
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> tmp;
vector<vector<int>> res;
sort(candidates.begin(), candidates.end());
backtrack(res,tmp,candidates,target,0);
return res;
}
void backtrack(vector<vector<int>>& res,vector<int>& tmp, vector<int>& candidates,
int target, int start)
{
if(target<0) return;
if(target ==0)
{
res.push_back(tmp);
return;
}
for(int i=start;i<candidates.size();i++)
{
tmp.push_back(candidates[i]);
backtrack(res,tmp,candidates,target-candidates[i],i);
tmp.pop_back();
}
}
040 组合总和II
给定一个数组有重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
解答：
因为有数组有重复所以要去重，因为只能用一次所以backtrack时需要+1防止自环。
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> tmp;
vector<vector<int>> res;
sort(candidates.begin(),candidates.end());
backtrack(res,tmp,candidates,target,0);
return res;
}
void backtrack(vector<vector<int>>& res,vector<int>& tmp,vector<int>& candidates,
int target,int start)
{
if(target<0) return;
if(target==0)
{
res.push_back(tmp);
return;
}
for(int i=start;i<candidates.size();i++)
{
if(i>start&&candidates[i]==candidates[i-1]) //上一个已经用过
continue;
tmp.push_back(candidates[i]);
backtrack(res,tmp,candidates,target-candidates[i],i+1);
tmp.pop_back();
//取巧去重
//set<vector<int>> s(res.begin(),res.end());
//res.assign(s.begin(),s.end());
}
}
077 组合
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解答：
按照直觉，先构建数组。注意比较的时候tmp.size()==k而不是start==k
vector<vector<int>> combine(int n, int k) {
vector<int> vec;
vector<vector<int>> res;
vector<int> tmp;
for(int i=1;i<=n;i++)
vec.push_back(i);
backtrack(res,tmp,vec,0,k);
return res;
}
void backtrack(vector<vector<int>>& res,vector<int>& tmp,
vector<int>& vec, int start,int k)
{
if(tmp.size()==k)
{
res.push_back(tmp);
return;
}
for(int i=start;i<vec.size();i++)
{
tmp.push_back(vec[i]);
backtrack(res,tmp,vec,i+1,k);
tmp.pop_back();
}
}
216 组合总和III
找出所有相加之和为 n\ 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解答：
这道题和077一样，需要自己创造一个nums容器出来，这样会比较清晰。
vector<int> tmp;
vector<vector<int>> res;
vector<int> nums;
vector<vector<int>> combinationSum3(int k, int n) {
for(int i=1;i<=9;i++)
nums.push_back(i);
backtrack(k,n,0);
return res;
}
void backtrack(int k,int n,int start)
{
if(n<0) return;
if(n==0&&k!=0) return;
if(n==0&&k==0)
{
res.push_back(tmp);
return;
}
for(int i=start;i<nums.size();i++)
{
tmp.push_back(nums[i]);
backtrack(k-1,n-nums[i],i+1);
tmp.pop_back();
}
}
078 子集
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
输入: nums = [1,2]
输出:
[
[1],
[2],
[1,2],
[]
]
解答：
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> tmp;
backtrack(res,tmp,nums,0);
return res;
}
void backtrack(vector<vector<int>>& res,vector<int>& tmp,
vector<int>& nums, int start)
{
res.push_back(tmp);
for(int i=start;i<nums.size();i++)
{
tmp.push_back(nums[i]);
backtrack(res,tmp,nums,i+1);
tmp.pop_back();
}
}
090 子集II
给定一个可能包含重复元素的整数数组 nums\，返回该数组所有可能的子集（幂集）。
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
解答：
两个要点：
- 查重，注意
i>start不是i>0 - 排序，不排序的话如果出现[4,4,4,1,4]这种，查重查不出来
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> res;
vector<int> tmp;
sort(nums.begin(), nums.end());
backtrack(res,tmp,nums,0);
return res;
}
void backtrack(vector<vector<int>>& res,vector<int>& tmp,
vector<int>& nums, int start)
{
res.push_back(tmp);
for(int i=start;i<nums.size();i++)
{
if(i>start&&nums[i]==nums[i-1]) continue;
tmp.push_back(nums[i]);
backtrack(res,tmp,nums,i+1);
tmp.pop_back();
}
}
093 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
解答：
这道题特别复杂，而且也不是传统的回溯套路。这里的for代表第n个字节，有三个剪枝条件，注意第二个的办法非常巧妙。
vector<string> restoreIpAddresses(string s) {
vector<string> res;
string tmp = "";
backtrack(s, res, tmp, 0);
return res;
}
void backtrack(string s, vector<string>& res,
string tmp, int n)
{
if(s.size()>3*(4-n)) return ;
if(n==4&&s.size()==0)
{
tmp.pop_back(); //去掉最后的'.'
res.push_back(tmp);
}
for(int i=1;i<=3;i++)
{
if(s.size()<i) break;
int val=stoi(s.substr(0,i));
if(i!=to_string(val).size()) break;
if(val>255) break;
tmp+=s.substr(0,i)+'.';
backtrack(s.substr(i),res,tmp,n+1);
tmp=tmp.substr(0,tmp.size()-i-1);
}
}
113 路径总和 II
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
[
[5,4,11,2],
[5,8,4,5]
]
解答：
112不需要存值，直接DFS就好，要存值最好用回溯模板。容器收集判断需要放在push后面！
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> tmp;
path(res, root, sum, tmp);
return res;
}
void path(vector<vector<int>>& res, TreeNode* root,
int sum, vector<int>& tmp)
{
//相较于112,需要记录
//采用深度优先的办法
if (root == NULL)
return;
tmp.push_back(root->val);
if (root->left == NULL && root->right == NULL)
{
if (root->val == sum)
res.push_back(tmp);
}
path(res, root->left, sum - root->val, tmp);
path(res, root->right, sum - root->val, tmp);
tmp.pop_back();
}
131 分割回文串
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
解答：
vector<vector<string>> res;
vector<string> tmp;
vector<vector<string>> partition(string s) {
backtrack(s, 0);
return res;
}
bool isPalindrome(string s)
{
string tmp = s;
reverse(tmp.begin(),tmp.end());
return s==tmp;
}
//start是开始计算的位置
void backtrack(string s, int start)
{
//如果不满足回文，start不会增长，start>s.size()-1意味着检验完毕
if (start > s.size() - 1)
{
res.push_back(tmp);
return;
}
//len是分割字符的长度
//这里必须小于等于，start=0，len=3，有效
for (int len = 1; len <= s.size() - start; len++)
{
//substr:pos+len
if (isPalindrome(s.substr(start, len)))
{
tmp.push_back(s.substr(start, len));
backtrack(s, start + len);
tmp.pop_back();
}
}
}
3. 排列问题
前面讲过，组合问题是按先后顺序进行，而排列则不是：前面用过的元素后面依然可能用到。所以排列问题需要用flag标记，组合则不需要。
046 全排列
给定一个没有重复数字的序列，返回其所有可能的全排列。
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解答：
我们需要用flag来做标记，用了某个元素就打上标记，回溯完以后就撤掉这个标记，重复利用。除了标记还需要注意int i = 0而不是组合问题中int i=start;
vector<vector<int>> res;
vector<int> tmp;
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> flag(nums.size(),false);
backtrack(nums,flag);
return res;
}
void backtrack(vector<int>& nums,vector<bool>& flag)
{
if(tmp.size()==nums.size())
{
res.push_back(tmp);
return;
}
for(int i=0;i<nums.size();i++)
{
if(flag[i]) continue;
tmp.push_back(nums[i]);
flag[i]=true;
backtrack(nums,flag);
flag[i]=false;
tmp.pop_back();
}
}
047 全排列II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
解答：
简单的去重没什么好说的，注意一定要sort排序，避免[4,4,4,1,4]这种情况。
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
vector<int> tmp;
//sort(nums.begin(), nums.end());
vector<bool> flag(nums.size(), false);
backtrack(nums, flag, res, tmp);
return res;
}
void backtrack(vector<int>& nums, vector<bool>& flag, vector<vector<int>>& res,
vector<int>& tmp)
{
if (tmp.size() == nums.size())
{
res.push_back(tmp);
return;
}
for (int i = 0; i < nums.size(); i++)
{
if (flag[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !flag[i - 1])
continue;
flag[i] = true;
tmp.push_back(nums[i]);
backtrack(nums, flag, res,tmp);
tmp.pop_back();
flag[i] = false;
}
}