回溯算法模板总结+力扣原题解析_回溯法的时间复杂度

回溯算法复杂度分析
回溯本质是遍历所有可能的情况，所以复杂度会比较高，但可以通过剪枝来优化。
子集问题：由于每个元素只有选择或者不选两种，所以遍历到每一种情况，时间复杂度为O(2^n),再加上构造的每一组子集都需要放入数组，需要o(n),所以总共O（n * 2^n）.空间复杂度，递归深度n,系统栈所用空间O(n)；
排列问题：时间复杂度O(N!)，第一层n个分枝，第二层每个分支又有n-1分支。所以nn-1n-1…*1=n!，空间复杂度O(N)
组合问题：组合问题就是一种子集问题（组合一般限制元素个数）

回溯算法通常用来解决的问题
组合问题：在n个数里面按照一定规则找出k个数的集合
排列问题：n个数按照一定规则排列，有几种排列方式
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个n个数的集合里有多少符合条件的子集

回溯法模板

void backtracking(参数) {
   
if (终⽌条件) 
{
   
	存放结果;
	return;
}
for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩） )
 {
   
	处理节点;
	backtracking(路径，选择列表); // 递归
	回溯，撤销处理结果
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

回溯算法的各种技巧和注意点
去重手法：
利用used数组记录元素是否访问过，实现同一树层和同一树枝去重,这里要注意used数组是作为函数参数传递，还是每一个for前重置以实现同一层用一个used，不同层用不同used

以下的题目都是力扣原题

组合问题

组合问题是不能交换元素位置的 也就是（1，2）（2，1）是同一个组合

组合

题目：给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

牢记回溯的本质是暴力解，枚举所有的情况，多叉树，利用for来遍历每个节点的所有分支。
由于前面同一个树枝上，前面选择过的元素后面不能再选，所以用startindex来控制选择的范围。

这个题也是套常规的回溯模板

但要加一个剪枝 就是如果剩下的元素已经不足还需要的元素就要没必要继续下去了

#include<iostream>
using namespace std;
#include<vector>

class Solution 
{
public:
    vector<vector<int>> res;
    vector<vector<int>> combine(int n, int k) 
    {
        vector<int> temp;
        backstacking(temp,n,k,1);
        return res;
    }
    void backstacking(vector<int>& temp,int n,int k,int StartIndex)
    {
        if (temp.size() == k)
        {
            res.push_back(temp);
            return;
        }

        //剪枝优化  如果剩下的元素已经不足还需要的元素就要没必要继续下去了
        //已经选择的元素个数 temp.size()  
        //还需要  k-temp.size()
        //集合至少要从n-(k-temp.size())+1
        for (int i = StartIndex; i <= n - (k - temp.size()) + 1; i++)
        {
            temp.push_back(i);
            backstacking(temp, n, k, i + 1);
            temp.pop_back();
        }
    }
};c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

组合问题3

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

说明：

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

组合问题在在做单层选择时要使用start_index,避免重复组合

剪枝：元素数量总和剪枝 for循环的范围剪枝

#include<iostream>
using namespace std;
#include<vector>
#include <unordered_set>
class Solution {
public
1
2
3
4
5