以Generate Parentheses为例，backtrack的题到底该怎么去思考？

比如Generate Parentheses这道经典的backtrack，代码如下：

1. public static List<String> generateParenthesis2(int n) {
   
2.         List<String> res = new ArrayList<>();
   
3.         backtrack("", res, n, n);
   
4.         return res;
   
5.     }
   
6. 
   
7.     public static void backtrack(String sublist, List<String> res, int left, int right) {
   
8.         if (left == 0 && right == 0) {
   
9.             res.add(sublist);
   
10.             return;
    
11.         }
    
12.         if (left > right)
    
13.             return;
    
14.         if (left > 0)
    
15.             backtrack(sublist + "(", res, left - 1, right);
    
16.         if (right > 0)
    
17.             backtrack(sublist + ")", res, left, right - 1);
    
18.     }

复制代码

实在是不知道这是怎么写出来的，为什么要这么写。。自己跟了一下debug才知道是怎么回事。。感觉和其他比较直观的backtrack不一样。。有童鞋能帮忙理一下这种backtrack题的诀窍和思路么？谢谢！！

所谓Backtracking都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集

所以你思考递归题时，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。即“ORT原则”（这个是我自己编的）

对于这道题，在任何时刻，你都有两种选择：
1. 加左括号。
2. 加右括号。

同时有以下限制：
1. 如果左括号已经用完了，则不能再加左括号了。
2. 如果已经出现的右括号和左括号一样多，则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。

结束条件是：
左右括号都已经用完。

结束后的正确性：
左右括号用完以后，一定是正确解。因为1. 左右括号一样多，2. 每个右括号都一定有与之配对的左括号。因此一旦结束就可以加入解集（有时也可能出现结束以后不一定是正确解的情况，这时要多一步判断）。

递归函数传入参数：
限制和结束条件中有“用完”和“一样多”字样，因此你需要知道左右括号的数目。
当然你还需要知道当前局面sublist和解集res。

因此，把上面的思路拼起来就是代码：

1. 
   
2. if (左右括号都已用完) {
   
3.   加入解集，返回
   
4. }
   
5. //否则开始试各种选择
   
6. if (还有左括号可以用) {
   
7.   加一个左括号，继续递归
   
8. }
   
9. if (右括号小于左括号) {
   
10.   加一个右括号，继续递归
    
11. }

复制代码

你帖的那段代码逻辑中加了一条限制：“3. 是否还有右括号剩余。如有才加右括号”。这是合理的。不过对于这道题，如果满足限制1、2时，3一定自动满足，所以可以不判断3。

这题其实是最好的backtracking初学练习之一，因为ORT三者都非常简单明显。你不妨按上述思路再梳理一遍，还有问题的话再说。

brn 发表于 2017-7-31 11:10
多写写和tree有关的题？

好的。谢谢建议。
有没有某个书的递归章节讲的比较详细。一步一步的。
例题是medium难度的。

解题思路。。。。多做

我也觉得backtrack很容易搞晕！看高人怎么解答的！

其实我觉得正着看更容易一些，就是使劲先往左边塞，左边塞满了就往右边塞。然后backtrack，删一个左边的，再重复上述策略。
class Solution {
public:
    /**
     * @param n n pairs
     * @return All combinations of well-formed parentheses
     */
    vector<string> generateParenthesis(int n) {
        // Write your code here
        if(n == 0)
            return {};

        vector<string> res;
        string line;
        dfs(line, n, 0, 0, res);
        return res;
    }

    void dfs(string line, int n, int left, int right, vector<string>& res){
        if(left == n && right == n){
            res.push_back(line);
            return;
        }

        if(left < n){
            line.push_back('(');
            dfs(line, n, left+1, right, res);
            line.pop_back();
        }

        if(right < left){
            line.push_back(')');
            dfs(line, n, left, right+1, res);
            line.pop_back();
        }

    }
};

stellari 发表于 2016-2-21 12:39
所谓Backtracking都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选 ...

thanks~每次你的回答都这么清晰！

stellari 发表于 2016-2-21 12:39
所谓Backtracking都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选 ...

感谢您的回复，真是超级清晰~顺便问一下，『有时也可能出现结束以后不一定是正确解的情况，这时要多一步判断』您说的这种情况我好像还没有遇到过，请问有什么例子可以借鉴么?多谢！

stellari 发表于 2016-2-21 12:39
所谓Backtracking都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选 ...

收藏这个答案》。

xiaozhuxiaozhu 发表于 2016-2-21 18:42
解题思路。。。。多做

递归真是理解无能。。
回溯法我就打算把那10来到排列组合 全背下来。

FightForTomo 发表于 2017-6-9 02:35
递归真是理解无能。。
回溯法我就打算把那10来到排列组合 全背下来。

你说的排列组合都是哪些？