一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1394|回复: 6
收起左侧

[算法题] 以Generate Parentheses为例,backtrack的题到底该怎么去思考?

[复制链接] |试试Instant~ |关注本帖
coldfire8 发表于 2016-2-20 19:44:27 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 coldfire8 于 2016-2-20 19:57 编辑

比如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.     public static void backtrack(String sublist, List<String> res, int left, int right) {
  7.         if (left == 0 && right == 0) {
  8.             res.add(sublist);
  9.             return;
  10.         }
  11.         if (left > right)
  12.             return;
  13.         if (left > 0)
  14.             backtrack(sublist + "(", res, left - 1, right);
  15.         if (right > 0)
  16.             backtrack(sublist + ")", res, left, right - 1);
  17.     }
复制代码
实在是不知道这是怎么写出来的,为什么要这么写。。自己跟了一下debug才知道是怎么回事。。感觉和其他比较直观的backtrack不一样。。有童鞋能帮忙理一下这种backtrack题的诀窍和思路么?谢谢!!

本帖被以下淘专辑推荐:

stellari 发表于 2016-2-21 12:39:12 | 显示全部楼层
所谓Backtracking都是这样的思路:在当前局面下,你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行(因为违反了某些限定条件),就返回;如果某种选择试到最后发现是正确解,就将其加入解集

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

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

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

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

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

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

因此,把上面的思路拼起来就是代码:

  1. if (左右括号都已用完) {
  2.   加入解集,返回
  3. }
  4. //否则开始试各种选择
  5. if (还有左括号可以用) {
  6.   加一个左括号,继续递归
  7. }
  8. if (右括号小于左括号) {
  9.   加一个右括号,继续递归
  10. }
复制代码
你帖的那段代码逻辑中加了一条限制:“3. 是否还有右括号剩余。如有才加右括号”。这是合理的。不过对于这道题,如果满足限制1、2时,3一定自动满足,所以可以不判断3。

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

评分

4

查看全部评分

回复 支持 4 反对 0

使用道具 举报

jigsaw_Becky 发表于 2016-2-20 19:52:33 | 显示全部楼层
我也觉得backtrack很容易搞晕!看高人怎么解答的!
回复 支持 反对

使用道具 举报

hongyuheng 发表于 2016-2-20 22:18:37 | 显示全部楼层
其实我觉得正着看更容易一些,就是使劲先往左边塞,左边塞满了就往右边塞。然后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();
        }

    }
};

回复 支持 反对

使用道具 举报

jigsaw_Becky 发表于 2016-2-21 12:48:13 | 显示全部楼层
stellari 发表于 2016-2-21 12:39
所谓Backtracking都是这样的思路:在当前局面下,你有若干种选择。那么尝试每一种选择。如果已经发现某种选 ...

thanks~每次你的回答都这么清晰!
回复 支持 反对

使用道具 举报

 楼主| coldfire8 发表于 2016-2-21 18:24:38 | 显示全部楼层
stellari 发表于 2016-2-21 12:39
所谓Backtracking都是这样的思路:在当前局面下,你有若干种选择。那么尝试每一种选择。如果已经发现某种选 ...

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

使用道具 举报

xiaozhuxiaozhu 发表于 2016-2-21 18:42:01 | 显示全部楼层
解题思路。。。。多做
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 17:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表