回溯算法或DFS中谨慎使用自增自减运算符去操作参数

 

  回溯算法或DFS中需要反复回到树的不同层,用于控制层的参数谨慎使用自增++和自减--运算符。

  这里直接贴一个leetcode第77题组合的回溯解法。https://leetcode-cn.com/problems/combinations/

 1 class Solution {
 2     vector<int> pathVec;
 3     vector<vector<int>> resultVec;
 4 public:
 5     vector<vector<int>> combine(int n, int k) {
 6         _backtrack(n,k,1);
 7         return resultVec;
 8     }
 9 
10     void _backtrack(int n,int k,int index)
11     {
12         if(k==0)
13         {
14             resultVec.push_back(pathVec);
15         }
16         else
17         {
18             for(int i=index;i<=n;++i)
19             {
20                 pathVec.push_back(i);
21                 _backtrack(n,k-1,i+1);
22                 pathVec.pop_back();
23             }
24         }
25         return;
26     }
27 };

  回溯函数_backtrack函数的第二个参数k代表第k个组合数,即多叉树的层数。当第21行k-1改成--k时,会造成树的层次混乱,当程序运行到第k层时,调用的下一层回溯函数如下:

假设i=1->3
//使用--k或者k--
_backtrack(n,k-1,2);
_backtrack(n,k-2,3);       //直接跳跃到第k-2层
_backtrack(n,k-3,4);        //直接跳跃到第k-3层

//正确使用k-1时
_backtrack(n,k-1,2);
_backtrack(n,k-1,3);
_backtrack(n,k-1,4);

 

上一篇:前端与 DSL


下一篇:17. 电话号码的字母组合