组合方面的题目，什么时候才需要for循环？

刷题刷到combination类，发现大多标准模板长这个样子，以combination sum 举例：

1. void dfs(candidates, target, start, cur, ans){
   
2.    if (target==0) ans.push_back(cur)； return;
   
3.    for (i=start ~ candidates.size()){
   
4.       if (target-candidates[i]<0) break;
   
5.       cur.push_back(candidates[i]);
   
6.       dfs (candidates, target - candidates[i], i, cur, ans);
   
7.       cur.pop_back();    }
   
8. }
   

复制代码

而我发现有以下两道题目的写法并没有start以及for循环这个结构啊，不像典型的回溯模板：
LC22 Generate Parentheses

1. void dfs(int left, int right, string& out, vector<string>& res){
   
2.   if(left>right) return;
   
3.   if(left==0 && right==0) res.push_back(out);
   
4.   if(left>0) dfs(left-1, right, out+'(', res);
   
5.   if(right>0) dfs(left, right-1, out+')', res);
   
6. }

复制代码

以及LC494 Target Sum

1. void dfs(vector<int>& nums, int d, int S, int& ans){
   
2.     if(d==nums.size()){
   
3.        if(S==0) ans++;
   
4.        return;
   
5.     }
   
6.     dfs(nums, d+1, S-nums[d], ans);
   
7.     dfs(nums, d+1, S+nums[d], ans);
   
8. }

复制代码

我不知道应不应该把这几道题归纳在一起，但真的感觉它们很像，可是不知道为何后两道题的做法没有套用经典回溯的模板（i.e.   for(i=start ...)  do something;  DFS();  undo something）
请大侠们指点下，什么情况用经典组合题模板，什么时候不要用？ 多谢多谢

这是backtracking。for loop 是为了尝试所有的possibility，一般subsets combination 一类的都要用。

在start 这个点，所有的candidate都可能是答案。所以要loop 所有candidate然后一个个的recurse。

leetcode上有个帖子叫backtracking general approach什么什么的你可以搜搜。

楼主您好，这个讲起来可能干文字将不太清楚！

是这样的。所有这种让你返回a list of combination的题目，都可以视作：“阶段性决策问题”

怎么理解？

阶段性：每一次递归操作可视作一个”阶段“，比如说你combination，从n中选k个。那么你这个backtracking算法，就肯定有k个阶段。
决策：每个阶段需要做出一次决策，对于combination来说，就是从n个数字(aka candidate)中选一个。也就是你写的那个循环。

所以你认为的递归套循环的模板是这么来的。

然后您问：啥时候用循环？这就要看你是怎么去model你的阶段，以及怎么去model你的决策的了。

对于这个Generate Parentheses来说，你要生成一个长度为2n的括号合法string，那你就有2n个阶段。划分清楚阶段，您的决策就显而易见了，您的决策就是2选1。所以这道题在做决策的时候不需要用到循环。您不妨再想想，如果这道题要你生成的不止一种括号，而是([{....，那您是不是还得写个循环？

所以说，要不要写循环并不是问题的本质，每个阶段的可选决策，才决定了每个递归要怎么写。

希望能帮到您。

要是有什么不清楚的地方也可以继续讨论（求大米

谢谢回复。我理解backtracking基本意思，而且如果题目是很接近combination ，subset和permutation都可以做，而且明白每一句是什么意思。

这里主要想对比以下LC22和LC494，感觉乍看上去也是这类的题目啊，可是做法上又有不同，所以希望大侠指点以下，这个不同的底层逻辑是什么~