什么时候不需要startIndex?
- 全排列：1在[1,2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了；
- 电话号码的字母组合：如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex；
- 二维的回溯--单词搜索。
如果是一个集合来求组合的话，就需要startIndex。
组合
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(int n, int k,int start)
{
if(path.size()==k)
{
res.push_back(path);
return;
}
for(int i=start;i<=(n-k+path.size()+1);i++)
{
path.push_back(i);
backtrack(n,k,i+1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtrack(n,k,1);
return res;
}
};优化的地方--剪枝：本题可以理解为横向遍历一棵树（n）及纵向遍历一棵树（k），对叶子节点的path加入res数组。在for循环中，i<=n-k+path.size()+1说明i的最大值是n-k+path.size()+1，即i从该值开始遍历，再大就不能凑够k个数字了。而backtrack的返回条件就是path凑够k个数的时候。
组合总和III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(int k,int n,int sum,int start)
{
if(sum>n)
{
return;
}
if(sum==n&&path.size()==k)
{
res.push_back(path);
return;
}
for(int i=start;i<=(9-k+path.size()+1);i++)
{
sum+=i;
path.push_back(i);
backtrack(k,n,sum,i+1);
path.pop_back();
sum-=i;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtrack(k,n,0,1);
return res;
}
};本题由于要求回溯过程中的和，因此多了一个参数sum。回溯返回有两个：sum>n或者sum==n&&path.size()==k。
电话号码的组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
class Solution {
public:
const vector<string> letters= {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
vector<string> res;
string path;
void backtrack(string& digits,int index)
{
if(index==digits.size())
{
res.push_back(path);
return;
}
int digit=digits[index]-'0';
string letter=letters[digit];
for(int i=0;i<letter.size();i++)
{
path+=letter[i];
backtrack(digits,index+1);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) {
return res;
}
backtrack(digits,0);
return res;
}
};注意本题有个测试用例是digits为空，则返回空，需要特殊处理。另外，由于本题是多个集合，所以不需要startIndex。index是遍历digits的下标，因此返回条件是index==digits.size()。
在回溯过程中，我们需要取出每一个字符数字对应的字符串,并且从0下标开始遍历。
组合总和-无限制重复被选取
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& candidates, int target,int sum,int start)
{
if(sum==target)
{
res.push_back(path);
return;
}
for(int i=start;i<candidates.size()&&sum+candidates[i]<=target;i++)
{
sum+=candidates[i];
path.push_back(candidates[i]);
backtrack(candidates,target,sum,i);
path.pop_back();
sum-=candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtrack(candidates,target,0,0);
return res;
}
};由于candidates 中的 同一个 数字可以 无限制重复被选取 ，因此在纵向的遍历backtrack中i并不需要加1，而是每次从start开始。start的意思是从candidates 第几个数开始取数，属于横向遍历。
注意这里的剪枝操作：for循环中,candidates[i]+sum<=target.
组合总和II-去重
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明： 所有数字（包括目标数）都是正整数。解集不能包含重复的组合
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtrack(vector<int>& candidates, int target,int sum,int start)
{
if(sum>target)
{
return;
}
if(sum==target)
{
res.push_back(path);
return;
}
for(int i=start;i<candidates.size()&&sum+candidates[i]<=target;i++)
{
if(i>start&&candidates[i]==candidates[i-1])
{
continue;
}
sum+=candidates[i];
path.push_back(candidates[i]);
backtrack(candidates,target,sum,i+1);
path.pop_back();
sum-=candidates[i];
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// 首先把给candidates排序，让其相同的元素都挨在一起。
sort(candidates.begin(), candidates.end());
backtrack(candidates,target,0,0);
return res;
}
};由于要进行去重操作，因此首先要把candidates进行排序操作。其次，在for循环中，i控制的是横向的遍历，因此当i>start时说明，已经至少遍历到第二个数字了。当后一个和前一个相等时，直接continue。
分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
class Solution {
public:
vector<vector<string>> res;
vector<string> path;
bool isPalidrom(string s,int left,int right)
{
// size_t left=0,right=s.size()-1;
while(left<=right)
{
if(s[left]!=s[right])
{
return false;
}
left++;right--;
}
return true;
}
void backtrack(string s,int start)
{
if(start==s.size())
{
res.push_back(path);
return;
}
for(int i=start;i<s.size();i++)
{
if(isPalidrom(s,start,i))
{
string str=s.substr(start,i-start+1);
path.push_back(str);
}
else
continue;
backtrack(s,i+1);
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
backtrack(s,0);
return res;
}
};时间复杂度和空间复杂度
子集问题分析
时间复杂度:O(n× 2^n)因为每一个元素的状态无外乎取与不取，一共 2^n种状态，每种状态都需要 O(n)的构造时间，最终时间复杂度为O(n× 2^n)。
空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为O(n)。
排列问题分析
时间复杂度：O(n×n!）因为一共n!种排列，每种排列都需要O(n)的构造时间，最终时间复杂度为O(n×n!)。
空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为O(n)。
