回溯注意点：回溯时间复杂度的计算与剪枝操作_回溯法剪枝策略

回溯的时间复杂度计算

计算回溯时间复杂度，我们可以使用如下公式：答案个数（叶子节点个数）×路径长度（搜索深度）

示例1：77.组合

void backtracking(vector<int>&path,vector<vector<int>>result,int n,int k,int startIndex){
   
    //终止
    if(path.size()==k){
   
        result.push_back(path);
        return;
    }
    //单层递归
    for(int i = startIndex;i<=n - (k - path.size()) + 1;i++){
   
        //加入路径
        path.push_back(i);
        //找到i开头的所有组合 12 13 14
        backtracking(path,result,n,k,i+1);
        //回溯,去掉1开始找2开头的，如果传入startIndex+1那么找2开头的就会出问题了
        path.pop();
    }
    return;
}
vector<vector<int>> combine(int n, int k) {
   
	vector<int>path;
    vector<vector<int>>result;
    int startIndex = 1;
    backtracking(path,result,n,k,startIndex);
    return result;
}
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

这道组合题目中，叶子节点个数也就是答案个数为$C_n^k$，搜索深度为k（因为需要k个数字），所以时间复杂度为k*$C_n^k$

严格来说，这个公式并不总是对所有回溯问题都适用。因为回溯问题的时间复杂度通常要考虑所有可能的搜索路径，而不仅仅是最终结果（叶子节点）。对于某些问题，可能存在大量的无效路径（即那些未导致有效解的路径），这些路径也会消耗计算资源。

在这个特定的问题中，这样做是正确的，因为每个搜索路径都直接对应一个结果，即从n中选取k个数的组合。所以在这个特定的场景下，可以将时间复杂度描述为k*$C_n^k$。但这种描述方法并不总是适用于所有的回溯问题。

示例2：216.组合总和Ⅲ

void backtracking(vector<int>& path,vector<vector<int>>&result,int k,int targetSum,int sum,