回溯算法或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);