正文

//伪代码
void backtracking(参数)//回溯函数

    if(终止条件)
        收集结果
        return;
    
    for(遍历所有集合的元素)
        处理结点，处理单个元素
        递归函数
        回溯操作(撤销处理的结点)

for循环是树里的横向遍历树，递归则是纵向遍历树。

递归回溯返回上一层，再收集下一个元素进行递归，直到返回。

结合下面的题目来理解。会更加清楚。

1.4 回溯算法可以解决的问题

组合问题： N个数⾥⾯按⼀定规则找出k个数的集合
切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式
⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集
排列问题： N个数按⼀定规则全排列，有⼏种排列⽅式
棋盘问题： N皇后，解数独等等

组合问题并不注重集合元素中的顺序如[1,2]和[2,1]，是一样的。排列注重集合元素的顺序[1,2]和[2,1]是两个集合

组合问题

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

抽象成的树结构：

1.确定回溯函数的参数和返回值

参数一个是集合n，一个是组合个数k，还需要一个startindex来控制范围。

void backtracking(int startindex,int n,int k);

2.递归终止条件

当收集的元素个数达到k时，收集结果返回。

        //终止条件
        if(path.size()==k)
            //搜集组合结果
            result.push_back(path);
            return;

3.单层的递归逻辑，收集结果和释放结果。

 for(int i=startindex;i<=n;i++)
            //操作，将单个元素放到数组中
            path.push_back(i);
            backtracking(i+1,n,k);
            //回溯，释放单个元素
            path.pop_back();

for循环每次从startindex开始，for循环确定了树的宽度。

由图可知，每次递归下一层从i+1开始。

path收集单个元素。递归完成回溯，释放收集的元素。

递归回溯返回上一层，再进行递归收集下一个元素。

class Solution 
public:
    vector<int> path;//收集结点，收集单个元素
    vector<vector<int>> result;//收集结果
    
    void backtracking(int startindex,int n,int k)
        //终止条件
        if(path.size()==k)
            //搜集组合结果
            result.push_back(path);
            return;
        
        for(int i=startindex;i<=n;i++)
            //操作，将单个元素放到数组中
            path.push_back(i);
            backtracking(i+1,n,k);
            //回溯，释放单个元素
            path.pop_back();
        
    
    vector<vector<int>> combine(int n, int k) 
        backtracking(1,n,k);
        return result;
    
;

剪枝：

剪枝思路：当后面的元素个数已经不够达到k值，时可以不用继续往下遍历了。例如：n=4，k=4。从n=2开始后面就不需要继续往下遍历了。

此时收集的元素个数path.size()；

剩下要收集的元素个数：k-path.size()

最大起始位置：n-(k-path.size())+1，从n-(k-path.size())+1开始到最后才正好收集K个。

为什么要加1？因为n时从1开始的。

class Solution 
public:
    vector<int> path;//收集结点，收集单个元素
    vector<vector<int>> result;//收集结果
    
    void backtracking(int startindex,int n,int k)
        //终止条件
        if(path.size()==k)
            //搜集组合结果
            result.push_back(path);
            return;
        
        for(int i=startindex;i<=n-(k-parh.size())+1;i++)
            //操作，将单个元素放到数组中
            path.push_back(i);
            backtracking(i+1,n,k);
            //回溯，释放单个元素
            path.pop_back();
        
    
    vector<vector<int>> combine(int n, int k) 
        backtracking(1,n,k);
        return result;
    
;

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。
示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

这一题与上面一题如出一辙，只是增加了一个条件，需要和等于n。

参数：

这里依旧用path来收集单个元素，res来收集结果。

k元素个数，n元素目标和

num每层收集的元素和

startindex开始位置(确定范围)，len最后位置(固定)

 void backtraking(int startindex,int len,int k,int n,vector<int>& path,vector<vector<int>>& res,int num)

递归终止：

当元素个数超过k时，此时不需要继续往下递归，立马返回

当元素和超过n时，此时不需要继续往下递归，立马返回

当元素个数等于k且和等于n时，搜集结果，返回。

//如果和大于n返回
if(num>n)
    return;

//如果元素个数大于k，返回
if(path.size()>k)
    return;

//收集结果
if(num==n&&path.size()==k)
    res.push_back(path);
    return ;

单层递归逻辑：

path收集单个元素，num求和，递归，最后回溯

 //单层递归逻辑
for(int i=startindex;i<=len-(k-path.size())+1;i++)
   num+=i;//求和
   path.push_back(i);//搜集单个元素
   backtraking(i+1,len,k,n,path,res,num);//递归
   num-=i;//回溯
   path.pop_back();//回溯

注意回溯：上面时加和push，回溯就要减和pop。

class Solution 
public:

    void backtraking(int startindex,int len,int k,int n,vector<int>& path,vector<vector<int>>& res,int num)
        //如果和大于n返回
        if(num>n)
            return;
        
        //如果元素个数大于k，返回
        if(path.size()>k)
            return;
        
        //收集结果
        if(num==n&&path.size()==k)
            res.push_back(path);
            return ;
        
        //单层递归逻辑
        for(int i=startindex;i<=len-(k-path.size())+1;i++)
            num+=i;//求和
            path.push_back(i);//搜集单个元素
            backtraking(i+1,len,k,n,path,res,num);//递归
            num-=i;//回溯
            path.pop_back();//回溯
        
    

    vector<vector<int>> combinationSum3(int k, int n) 

        vector<vector<int>> res;
        vector<int> path;
        backtraking(1,9,k,n,path,res,0);
        return res;


    
;

17电话号码的组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

确定回溯函数参数：

path搜集单个元素，res搜集结果，digits按键，start第几个个按键，len按键总个数

 void backtracing(string digits,int start,int len,string& path,vector<string>& res)

确定递归返回：

当path元素个数等于按键个数时，收集结果，返回

if(path.size()==len)
    res.push_back(path);
    return;

单层递归逻辑

先求出是哪个按键，遍历按键的所有字母情况。收集元素。

//用数组或者map可以保存按键和字母的对应关系
//下标对应按键的字母情况
string str[10]="","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz";
//注意递归不是增加的循环起始，而是走到下一个按键
int x=digits[start]-'0';//start按键字符转整形
for(int j=0;str[x][j]!=0;j++)//变量按键里字母的情况
   path.push_back(str[x][j]);//收集元素
   backtracing(digits,start+1,len,path,res);
   path.pop_back();//回溯

注意几个细节点：

1.用数组或者map保存按键余字母的所有情况

2.递归更新的不是循环的起始值，而是按键的下一个。题意就是收集不同按键的字母的所有情况。

class Solution 
public:
    //下标对应按键的字母情况
    string str[10]="","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz";

    void backtracing(string digits,int start,int len,string& path,vector<string>& res)
        if(path.size()==len)//按键个数等于收集元素个数
            res.push_back(path);
            return;
        

        //注意递归不是增加的循环起始，而是走到下一个按键
        int x=digits[start]-'0';//start按键字符转整形
        for(int j=0;str[x][j]!=0;j++)//变量按键里字母的情况
            path.push_back(str[x][j]);//收集元素
            backtracing(digits,start+1,len,path,res);
            path.pop_back();//回溯
        
        
    

    vector<string> letterCombinations(string digits) 
        int len=digits.size();
        vector<string> res;
        if(len==0)
            return res;
        
        string path;
        
        backtracing(digits,0,len,path,res);

        return res;
    
;

39. 组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。

对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

示例 1：

输入: candidates = [2,3,6,7], target = 7
输出: [[7],[2,2,3]]

这上面的组合问题有点不同，是可以重复获取数字，但是，由于是组合问题，不考虑顺序，只能从一个数后面位置开始取数，不能从前面取数。

函数参数：

void  backtracing(vector<int>& candidates,int target,int num,int start,int len,
vector<vector<int>>& result,vector<int>& path)

candidates为集合，target为目标和，num为当前求的和，start从集合Negev元素开始，len集合长度，result收集结果，path收集单个元素。

递归终止条件：

if(num>target)//当前和大于目标和，不需要继续往下算
    return;

if(num==target)//等于目标和，搜集结果
    result.push_back(path);
    return;

单层递归逻辑：

收集结点和回溯

重复体现在每次循环开始不是i+1，而是i。

//重复体现在start，不是i+1，而是从i开始
for(int i=start;i<len;i++)
    path.push_back(candidates[i]);//收i结果
    num+=candidates[i];
    backtracing(candidates,target,num,i,len,result,path);
    path.pop_back();//回溯
    num-=candidates[i];

class Solution 
public:
    void  backtracing(vector<int>& candidates,int target,int num,int start,int len,vector<vector<int>>& result,vector<int>& path)
        if(num>target)//当前和大于目标和，不需要继续往下算
            return;
        
        if(num==target)//等于目标和，搜集结果
            result.push_back(path);
            return;
        
        //重复体现在start，不是i+1，而是从i开始
        for(int i=start;i<len&&num+candidates[i]<=target;i++)
            path.push_back(candidates[i]);//收i结果
            num+=candidates[i];
            backtracing(candidates,target,num,i,len,result,path);
            path.pop_back();//回溯
            num-=candidates[i];
        
    



    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
        vector<vector<int>> result;
        vector<int> path;
        int len=candidates.size();
        backtracing(candidates,target,0,0,len,result,path);
        return result;
    
;

这里有一个剪枝：

回溯剪枝一般在for循环中，如果num + candidates [i] >target 不继续往下回溯。但是要先排序，如果后面又小的数，符合条件也不会去回溯了。

class Solution 
public:
    void  backtracing(vector<int>& candidates,int target,int num,int start,int len,vector<vector<int>>& result,vector<int>& path)
        if(num>target)//当前和大于目标和，不需要继续往下算
            return;
        
        if(num==target)//等于目标和，搜集结果
            result.push_back(path);
            return;
        
        //重复体现在start，不是i+1，而是从i开始
        for(int i=start;i<len&&num+candidates[i]<=target;i++)
            path.push_back(candidates[i]);//收i结果
            num+=candidates[i];
            backtracing(candidates,target,num,i,len,result,path);
            path.pop_back();//回溯
            num-=candidates[i];
        
    



    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
        //剪枝要先排序，不然后面有小的，符合条件也不回溯了。
        sort(candidates.begin(),candidates.end());
        vector<vector<int>> result;
        vector<int> path;
        int len=candidates.size();
        backtracing(candidates,target,0,0,len,result,path);
        return result;
    
;

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

该题重点：1.元素不可以重复获取

2.给的集合candidates 中有相同元素，但是结果集合中不能出现组合相同的组合

元素不可以重复获取：可以调整每次回溯for循环中，i开始的范围。

给的集合candidates 中有相同元素，但是结果集合中不能出现组合相同的组合：一开始我想的是重复元素利用set去重，在去回溯。但是会忽略一些结果，比如： [10,1,2,7,6,1,5]就忽略了[1,1,6]。

        那么问题来了，我们是要同⼀树层上使⽤过，还是统⼀树枝上使⽤过呢？
        回看⼀下题⽬，元素在同⼀个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
        所以我们要去重的是同⼀树层上的“使⽤过”，同⼀树枝上的都是⼀个组合⾥的元素，不⽤去重。

        强调⼀下，树层去重的话，需要对数组排序！

  排序后，回溯同一层中取到相同元素就不要继续往下回溯了，因为会出现组合相同的情况。

解决：先排序，如果该开始收集的数和之前感慨是搜集的数相同，就不回溯了。看图好理解。

注意：for循环时树的宽度，递归式树的深度。去重，是在for循环里去重。同一层用到同一个数。会有同样的组合，而不是同一路径。比如下图，同一层用到同一个数就会有[1...]，[1...]一样的组合。同一路径用到同一个数，就是[1，1...]。

函数参数：

candidates给的集合，target目标和，num当前和，start确定开始遍历位置，len结合长度，result收集结果，path收集单个结点。

backtracing(vector<int>& candidates,int target,int start,int len,int num,
vector<vector<int>>& result,vector<int>& path)

递归终止条件：

//大于就返回
if(num > target)
    return ;

//收集结果
if(num == target)
    result.push_back(path);
    return ;

单层递归逻辑：

这里有一个剪枝：

回溯剪枝一般在for循环中，如果num + candidates [i] >target 不继续往下回溯。

//剪枝 num + candidates [i] >target 不继续往下回溯。
for(int i=start; i<len && num+candidates[i]<=target; i++)
    //一层中有相同的就不回溯(会有相同结果，之前已经遍历过这种情况)，不是同一路径，
    if(i>start&&candidates[i]==candidates[i-1])
        continue;
    
    num+=candidates[i];
    path.push_back(candidates[i]);
    backtracing(candidates,target,i+1,len,num,result,path);
    num-=candidates[i];
    path.pop_back();

class Solution 
public:
    void backtracing(vector<int>& candidates,int target,int start,int len,int num,vector<vector<int>>& result,vector<int>& path)
        //大于就返回
        if(num > target)
            return ;
        
        //收集结果
        if(num == target)
            result.push_back(path);
            return ;
        
        for(int i=start; i<len && num+candidates[i]<=target; i++)
            //一层中有相同的就不回溯(会有相同结果，之前已经遍历过这种情况)，不是同一路径，
            if(i>start&&candidates[i]==candidates[i-1])
                continue;
            
            num+=candidates[i];
            path.push_back(candidates[i]);
            backtracing(candidates,target,i+1,len,num,result,path);
            num-=candidates[i];
            path.pop_back();
        

    
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
        //要先排序
        sort(candidates.begin(),candidates.end());
        int len=candidates.size();
        vector<vector<int>> result;
        vector<int> path;
        backtracing(candidates,target,0,len,0,result,path);
        return result;

    
;

分割问题

分割问题注意切割线在哪，或者说时哪个。切割线一般是循环开始startindex。

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

回文串是正着读和反着读都一样的字符串。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

函数参数：

字符串s，循环开始位置startindex，字符串长度，收集结果result，收集字符串path。

 void backtracing(string& s,int startindex,int len,vector<vector<string>>& result,vector<string>& path)

上一次切割线位置为startindex。

如图

递归终止条件：

如例子，当切割线到最后，就收集结果

//当切割线到最后时，递归结束
if(startindex==len)
    result.push_back(path);
    return;

单层递归逻辑：

先取得子串，由于上一次切割线位置为startindex，子串长度为i-startindex+1。获取子串用substr函数，第一个参数为起始位置，第二个参数为子串长度。

判断子串是否为回文串，是就回溯并且收集子串。

//分割线在startindex位置
for(int i=startindex;i<len;i++)
     //获取子串
     string tmp=s.substr(startindex,i-startindex+1);
     //判断子串是否是回文串
     if(JudgePal(tmp))
        path.push_back(tmp);
        backtracing(s, i+1, len, result, path);
        path.pop_back();

class Solution 
public:
    //判断一个字符串是否是字符串
    bool JudgePal(string& str)
        int left=0;
        int right=str.size()-1;
        while(left<right)
            if(str[left]!=str[right])
                return false;
            
            left++,right--;
        
        return true;

    
    
    void backtracing(string& s,int startindex,int len,vector<vector<string>>& result,vector<string>& path)
        //当切割线到最后时，递归结束
        if(startindex==len)
            result.push_back(path);
            return;
        
        //分割线在startindex位置
        for(int i=startindex;i<len;i++)
            //获取子串
            string tmp=s.substr(startindex,i-startindex+1);
            //判断子串是否是回文串
            if(JudgePal(tmp))
                path.push_back(tmp);
                backtracing(s, i+1, len, result, path);
                path.pop_back();
            
        

    

    vector<vector<string>> partition(string s) 

        vector<vector<string>> result;
        vector<string> path;

        int len=s.size();
        backtracing(s,0,len,result,path);

        return result;

    
;

93. 复原 IP 地址

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 IP 地址。你可以按任何顺序返回答案。

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

该题题时切割问题，'.'逗号位置就是切割位置。限制条件要将字符串分为4段，每段字符对应的整数要求大于等于0，小于等于255。并且每段长度大于1时，第一个不能为0。每段之间以'.'逗号隔开。

图片取至代码随想录

注意：由题意，IP地址为4段，每段转化为整数后处于0~255之间。假设每段都是255，字符串长度最多为12个，当超过12时，肯定不能转化为IP地址。

函数参数：

s为字符串，startindex为字符起始位置，也是上一次的切割位置。len字符串长度，result收集IP字符串，path单个符合条件IP字符串。

void backtracing(string& s,int startindex,int len,vector<string>& result,string& path)

递归终止条件：

单层逻辑，我在每个符合条件的子串后面都加了一个'.'逗号。当IP长度等于s长度+4时，并且切割到最后，收集结果返回。未切割到最后，直接返回。

//我在每段后面都加了一个'.'，
//当IP长度等于s+4，但是没有切割到最后
//IP不符合条件，直接返回
if(path.size()==len+4&&startindex<len)
    return;

//当IP长度等于s+4，切割到最后
//IP符合条件，收集结果后，返回
if(path.size()==len+4&&startindex==len)
    path.pop_back();
    result.push_back(path);
    return;

单层递归逻辑：

先获取子串，注意startindex是上一次的切割位置。判断子串是否在0~255之间。如果子串长度大于1，子串第一个字符不能为0。

回溯，要将子串全部pop出来。

for (int i = startindex; i<len; i++)
	//切割子串
	string tmp = s.substr(startindex, i - startindex + 1);
	//子串转为C字符串
	const char* str = tmp.c_str();
	//转化成整数
	int x = atoi(str);
	//在范围内
	if ((x <= 255 && x >= 0))
		//子串长度大于1，第一个不能为0
		if (tmp[0] == '0'&&tmp.size()>1)

		
		//收集子串
		else
			//形成IP
			path += str;
			path += '.';

			backtracing(s, i + 1, len, result, path);
			//取出'.'
			path.pop_back();
			//将收集的子串pop
			while (path.size()>0 && path[path.size() - 1] != '.')
				path.pop_back();

总代码：

class Solution 
public:
    void backtracing(string& s,int startindex,int len,vector<string>& result,string& path)
        if(path.size()==len+4&&startindex<len)
            return;
        
        if(path.size()==len+4&&startindex==len)
            path.pop_back();
            result.push_back(path);
            return;
        


        for(int i=startindex;i<len;i++)
            //切割子串
            string tmp=s.substr(startindex,i-startindex+1);
            //子串转为C字符串
            const char* str=tmp.c_str();
            //转化成整数
            int x=atoi(str);
            //在范围内
            if((x<=255&&x>=0))
                //子串长度大于1，第一个不能为0
                if(tmp[0]=='0'&&tmp.size()>1)

                
                //收集子串
                else
                    //形成IP
                    path+=str;
                    path+='.';

                    backtracing(s,i+1,len,result,path);
                    //取出'.'
                    path.pop_back();
                    //将收集的子串pop
                    while(path.size()>0&&path[path.size()-1]!='.')
                        path.pop_back();
                    
                
               
                
            
        
    



    vector<string> restoreIpAddresses(string s) 
        vector<string> result;
        string path;
        int len=s.size();
        //长度大于12.不能形成IP
        if(len>12)
            return result;
        
        backtracing(s,0,len,result,path);

        return result;
    
;

求子集问题

子集问题也适用于回溯算法，与组合和切割问题不同的是，组合和切割问题都是在叶节点收集结果，子集问题是收集每一个结点的结果。

子集问题也是一种组合问题，不考虑顺序。所以按照模板，for循环从startindex开始，startindex递归更新是从i+1开始。

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

按照例子，我们发现每一个结点，就是我们需要的结果。

函数参数：

nums数组集合，start开始位置，从nums中的哪个位置开始，len数组长度，result收集结点结果，path收集每一个数字，相当于结点。

void backtracing(vector<int>& nums,int start,int len,
vector<vector<int>>& result,vector<int>& path)

递归终止条件：

nums中遍历开始位置后面已经没有元素时，返回。

开始位置时start，当start==len时，后面没有元素了。

其实这里也不要写递归返回，因为for循环循环条件是i<len，当start>len时不会进入循环，直接返回。

if(start>=len)
    return ;

单层递归逻辑：

收集元素，递归和回溯，path相当于结点。

for(int i=start;i<len;i++)
    path.push_back(nums[i]);//收集子集元素
    backtracing(nums,i+1,len,result,path);//递归
    path.pop_back();//回溯

由于树的每一个结点都要收集：每次递归进入循环，都要收集结果。

class Solution 
public:
    void backtracing(vector<int>& nums,int start,int len,vector<vector<int>>& result,vector<int>& path)
        //收集结点
        result.push_back(path);
        //可以不写
        // if(start>=len)
        //     return ;
        // 

        for(int i=start;i<len;i++)
            path.push_back(nums[i]);//收集子集元素
            backtracing(nums,i+1,len,result,path);//递归
            path.pop_back();//回溯
        
    

    vector<vector<int>> subsets(vector<int>& nums) 

        vector<vector<int>> result;
        vector<int> path;
        int len=nums.size();
        backtracing(nums,0,len,result,path);
        return result;
    
;

491. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

根据示例发现，该结果求的是子集，但是需要去重。比如：不去重，[4，6，7]会出现两次。

去重不能像上面的一个组合问题一样，先排序后去重，排序后，就不能得到和想在相同顺序的递增子序列了。

并且去重是去除同一层相同的值，排序后可以比较前后，但是这里不能排序，可以用哈希表或者是一个数组记录，同一层是否已经使用过该元素。

函数参数：

由于同一元素不能重复取，取元素范围从startindex开始，每次递归从i+1开始。

 void backtracing(vector<int>& nums,int startindex,int len,
vector<vector<int>>& result,vector<int>& path)

递归返回：

当startindex到数组最后，没有元素，递归返回。递归返回条件不用写，for循环，循环条件是再最后，会直接返回。

单层递归逻辑：

当path中没有元素要插入元素，当path最后一个元素比nums的第i个元素大于或者等于，插入元素。

还需要用哈希表或者建立一个数组。判断同一层是否使用相同元素。

 for(int i=startindex;i<len;i++)
            //当path元素不是一个并且小于path的值
            //当同一层有相同的
            if(path.size()>0&&nums[i]<path[path.size()-1]||map[nums[i]+100]==1)
                continue;
            
            //元素只有一个，和nums[i]>path最后一个
            //user.insert(nums[i]);
            map[nums[i]+100]=1;
            path.push_back(nums[i]);                   
            backtracing(nums,i+1,len,result,path);
            path.pop_back();

难点主要是同一层不能使用相同元素，并且不能排序。用数组或者哈希表记录。

同一层是在for循环里。递归会重新定义。

class Solution 
public:
    void backtracing(vector<int>& nums,int startindex,int len,vector<vector<int>>& result,vector<int>& path)
        if(path.size()>1)
            result.push_back(path);
        
        //去除同一层里相同的
        //同一层相同的是树的宽度，for循环里
        //每一次递归，是树的高度，都会重新定义
        //unordered_set<int> user;//去重
        int map[201]=0;
        
        for(int i=startindex;i<len;i++)
            //当path元素不是一个并且小于path的值
            //当同一层有相同的
            if(path.size()>0&&nums[i]<path[path.size()-1]||map[nums[i]+100]==1)
                continue;
            
            //元素只有一个，和nums[i]>path最后一个
            //user.insert(nums[i]);
            map[nums[i]+100]=1;
            path.push_back(nums[i]);                   
            backtracing(nums,i+1,len,result,path);
            path.pop_back();

        
    


    vector<vector<int>> findSubsequences(vector<int>& nums) 
        int len=nums.size();
        vector<vector<int>> result;
        vector<int> path;
        backtracing(nums,0,len,result,path);
        return result;

    
;

排列问题

46. 全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

排列时有序的，元素相同顺序不同的集合是不同的集合。

所以排列不能像组合一样，每次循环从startindex开始，而是每次从0 开始。集合[1，2]，[1，2]和[2，1]是两个不同的集合。1使用完，选2的时候还会要使用1，所以每次循环从0开始。

还需要用一个数组记录元素是否使用过，不然会出现重复元素的情况。

抽象成树形结构：

函数参数：

result收集结果，path收集单个元素，key元素是否使用的标志。

    vector<vector<int>> result;
    vector<int> path;
    void backtracing(vector<int>& nums,int len,vector<int>& key)

递归出口：

全排列，当收集元素个数等于数组元素个数时，收集结果，返回。

        if(path.size()==len)
            result.push_back(path);
            return;

单层递归逻辑：

判断是否使用过，未使用，push进path，将该元素标记为使用过。再递归

回溯：pop出元素，将该元素回溯为未使用。

 //全排列开始从0开始，因为注重顺序
        for(int i=0; i<len; i++)
            //未使用
            if(key[i]==0)
                path.push_back(nums[i]);
                //表示未使用过
                key[i]=1;
                backtracing(nums,len,key);
                //回溯
                path.pop_back();
                //回溯为未使用
                key[i]=0;

class Solution 
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracing(vector<int>& nums,int len,vector<int>& key)
        if(path.size()==len)
            result.push_back(path);
            return;
        
        //全排列开始从0开始，因为注重顺序
        for(int i=0; i<len; i++)
            //未使用
            if(key[i]==0)
                path.push_back(nums[i]);
                //表示未使用过
                key[i]=1;
                backtracing(nums,len,key);
                //回溯
                path.pop_back();
                //回溯为未使用
                key[i]=0;
            
        
    

public:
    vector<vector<int>> permute(vector<int>& nums) 
        //记录是否使用过，0未使用，1使用过
        vector<int> key;
        int len=nums.size();
        key.resize(len);
        backtracing(nums,len,key);
        return result;

    
;

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

因为有重复的元素，这里涉及到需要去重的操作。

去重的操作和组合去重的操作类似，由于这里没有严格规定连个数之间的相对位置。可以先排序后去重。同一层元素相同，不进行排列。

如果前后两元素相等，并且，前面这个元素没有使用，说明还会拿前面的元素，会有相同的结果。此时不进行排列。

            //如果前一个没使用过，并且还和现在一样，会出现相同结果
            if(i>0&&usered[i-1]==0&&nums[i]==nums[i-1])
                continue;

其它排列情况和上面相同

class Solution 
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracing(int len,vector<int>& nums,vector<int>& usered)
        if(path.size()==len)
            result.push_back(path);
            return;
        
        for(int i=0; i<len; i++)
            //如果前一个没使用过，并且还和现在一样，会出现相同结果
            if(i>0&&usered[i-1]==0&&nums[i]==nums[i-1])
                continue;
            

            if(usered[i]==0)
                usered[i]=1;
                path.push_back(nums[i]);
                backtracing(len,nums,usered);
                usered[i]=0;
                path.pop_back();
            
        
    
    static bool cmp(int a, int b)
        return a<b;
    
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) 
        //先排序，将相同的元素放一起
        sort(nums.begin(),nums.end(),cmp);
        int len=nums.size();
        //标记元素是否使用
        vector<int> usered;
        usered.resize(len);
        backtracing(len,nums,usered);
        return result;

    
;

重新安排行程

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例 1：
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

这道题⽬有⼏个难点：
        1. ⼀个⾏程中，如果航班处理不好容易变成⼀个圈，成为死循环
        2. 有多种解法，字⺟序靠前排在前⾯，让很多同学望⽽退步，如何该记录映射关系呢？
        3. 使⽤回溯法（也可以说深搜）的话，那么终⽌条件是什么呢？
        4. 搜索的过程中，如何遍历⼀个机场所对应的所有机场。

1. ⼀个⾏程中，如果航班处理不好容易变成⼀个圈，成为死循环?

为什么是这样？比如 ["JFK"，"NRT"]，["NRT"，"JFK"]。起始只有两个航班，两个航班起点和重点是相反的，这样会形成一个循环，最终递归返回导致错误的结果。

所以我们每次用完一个航班就需要删除这个航班或者标记。

2..如何确定映射关系？

这里要确定起始位置和终止位置的映射关系，并且出现的起始位置会有重叠。

如果直接用multimap<string，string>，或者unordered_map<string，multiset<string>> 在删除时，会导致迭代器失效。(multimap<起始位置，终止位置>，unordered_map<起始位置，multiset<终止位置>>

我们可以使用unordered_map<string，map<string，int>>，含义：unordered_map<起始位置，map<终止位置，起始位置相同的航班数>>，用航班个数记录是否还能用该航班，不用做删除操作。

        //key<起始位置，<终止位置，航班次数>>
        unordered_map<string,map<string,int>> key;

3. 终止条件

每次都会要走一个航班，但是起始还有一个"JFK"，所以当收集结果个数等于航班数加1，返回。

        if(result.size()==ticketsnum+1)
            return true;

4. 通过回溯法来遍历各机场

递归参数

ticketsnum表示航班数

 vector<string> result;//保持结果
 //返回值bool，因为我们只需要找一条线
 bool backtracing(unordered_map<string,map<string,int>>& key, int ticketsnum)

返回值为bool，由题意，至少存在一种合理行程，我们只要找到该行程再一直返回就好了。

result和key都需要初始化：

由题意，行程由"JKF"出发。

key记录内一个航班起始和终止，并且相同起点，的航班数。

        for(int i=0; i<ticketsnum; i++)
            key[tickets[i][0]][tickets[i][1]]++;          
        
        result.push_back("JFK");

递归终止条件

每次都会要走一个航班，但是起始还有一个"JFK"，所以当收集结果个数等于航班数加1，返回。

        if(result.size()==ticketsnum+1)
            return true;

单层递归逻辑

这里有一个很隐晦的条件，通过result里的值作为起点再key中找终点。得到c。

再判断该位置是否还能用。

        //key[result[result.size()-1]是通过起点找终点，
        for(pair<const string,int>& c : key[result[result.size()-1]])
            //看是否还能用
            if(c.second>0)
                c.second--;
                result.push_back(c.first);
                if(backtracing(key,ticketsnum)==true)
                    return true;
                
                c.second++;
                result.pop_back();
            
        
        return false;

注意：pairstring⾥要有const，因为map中的<key，value>的key是不可修改的，所以是 pair<const string, int> 。

class Solution 
    vector<string> result;
    //返回值bool，因为我们只需要找一条线
    bool backtracing(unordered_map<string,map<string,int>>& key, int ticketsnum)
        if(result.size()==ticketsnum+1)
            return true;
        
        //key[result[result.size()-1]是通过起点找终点，
        for(pair<const string,int>& c : key[result[result.size()-1]])
            //看是否还能用
            if(c.second>0)
                c.second--;
                result.push_back(c.first);
                if(backtracing(key,ticketsnum)==true)
                    return true;
                
                c.second++;
                result.pop_back();
            
        
        return false;
    

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) 
        //key<起始位置，<终止位置，航班次数>>
        unordered_map<string,map<string,int>> key;
        int ticketsnum=tickets.size();
        for(int i=0; i<ticketsnum; i++)
            key[tickets[i][0]][tickets[i][1]]++;          
        
        result.push_back("JFK");        
        backtracing(key, ticketsnum);
        return result;

        
    
    
;

初识“回溯算法”讲解及leetcode对应例题解析(代码片段)

初识“回溯算法”讲解及LeetCode对应例题解析回溯算法1、回溯算法的概念2、回溯算法的一般解题思路3、解决问题的方法例题一：二叉树中和为某一值的路径（1）题目描述（2）题目分析（3）代码实现... 查看详情

算法----leetcode回溯系列问题题解(代码片段)

回溯法回溯1.什么是回溯?2.回溯法解决的问题3.回溯法的模板LeetCode题目列表组合问题77.组合216组合总和III17.电话号码的字母组合39.组合总和40.组合总和II分割问题131.分割回文串93.复原IP地址子集问题78.子集90.子集II排列问题46.全... 查看详情

[22].括号生成(代码片段)

[22].括号生成题目算法设计：回溯算法设计：空间换时间题目传送门：https://leetcode.cn/problems/generate-parentheses/ 算法设计：回溯括号问题可以分成俩类：括号的合法性判断，主要是用栈括号的合法生成，... 查看详情

[回溯算法]leetcode40.组合总和ii(c实现)(代码片段)

题目代码/***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothreturnedarrayand*columnSizesarraymustbemalloced,assumecallercallsfree().*/int*path;int 查看详情

算法学习之回溯法--迷宫问题(代码片段)

题目描述定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示： int maze[5][5] = 0, 1, 0, 0, 0, &n 查看详情

算法入门（回溯算法）(代码片段)

当学习完递归后，就可以来学习与理解它好兄弟回溯了。回溯算法比较抽象，小编就以自己学习的角度来分析了！回溯与递归有什么关系递归与回溯是相辅相成的，回溯算法在递归之后，（可以理解没... 查看详情

算法训练之回溯法(代码片段)

什么是回溯法题目1已知完成一个简单的工作需要1天，中等难度，需要2天，困难需要4天，如果未来有n个工作日，请返回所以可能的任务排列数。如输入：3输出:3这里3表示3种方案，[1,1,1],[1.2],[2,1]解法1... 查看详情

算法每日一题(代码片段)

文章目录题目描述利用回溯那就利用动态规划题目描述Youaregivenanintegerarraycoinsrepresentingcoinsofdifferentdenominationsandanintegeramountrepresentingatotalamountofmoney.Returnthenumberofcombinationsthatmakeupthatamount.Iftha 查看详情

[回溯算法]leetcode216.组合总和iii(c实现)(代码片段)

题目代码int*path;intpathTOP;int**ans;intansTOP;voidbacktracking(inttargetsum,intk,intsum,intsatrtindex)inti=0;if(sum>targetsum)//剪枝操作return;if(k==pathTOP)if(sum==targetsum)int*temp=(int*)malloc(sizeof( 查看详情

[回溯算法]leetcode17.电话号码的字母组合(c实现)(代码片段)

题目代码/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/char*path;intpathTOP;char**result;intresultTOP;char*letterMap[10]="","","abc","def"," 查看详情

一文通数据结构与算法之——回溯算法+常见题型与解题策略+leetcode经典题(代码片段)

文章目录回溯算法1基本内容1.1回溯算法的框架1.2回溯核心思想1.3回溯法解决的问题1.4题目列表1.4常见问题分析2经典力扣题2.1全排列问题2.1.1没有重复元素的全排列2.1.2含重复元素的递归全排列2.2子集问题2.2.1不含重复元素的子集2... 查看详情

算法设计与分析实训(代码片段)

...1.题目2.目的3.内容4.需求分析5.两种算法5.1动态规划法5.2回溯法6.总结及心得体会1.题目0-1背包问题2.目的课程设计的目的是训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发... 查看详情

核心算法5回溯算法(代码片段)

回溯算法可以看成走迷宫，不知道出口在哪，所以只能不断深入，尝试不同的路线。但一旦找到出口便可以回溯到起点，辩清路线。回溯算法遍历所有排序方式经典问题的组合查找单词问题八皇后问题解数独回溯算法简单来说，... 查看详情

理解回溯法及例题分析(代码片段)

1、对回溯算法的理解回溯法(探索与回溯法)是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术... 查看详情

回溯算法(代码片段)

回溯算法回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但... 查看详情

算法总结二叉树常见算法题目及解题思路汇总(代码片段)

二叉树算法总结主要解决思路：递归自底向上分治栈或队列常见算法题二叉树结构定义如下publicclassTreeNodeintval;TreeNodeleft;TreeNoderight;TreeNode(intx)val=x;1、前序遍历LeetCode144给定一个二叉树，返回它的前序遍历。递归解法pub... 查看详情

[动态规划与回溯算法]路径问题(代码片段)

第一层三角矩阵题目描述：大白话：计算顶部到底步的路径，路径值相加求这个三角形的路径和中值最小，且每一步看一移动到当前位置的下一行，或下一行下一个如index:(i,j)-->(i-1,j)或(i-1,j-1)思路1:“三”状... 查看详情

回溯算法(代码片段)

百度百科解释:回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目... 查看详情