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

本文主要是介绍回溯算法或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);

这篇关于回溯算法或DFS中谨慎使用自增自减运算符去操作参数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！