回溯算法最佳实践：括号生成 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：回溯算法最佳实践：括号生成

评论礼仪 见这里，违者直接拉黑。

[MichaelXoXo]

这里的公式渲染有问题 $\frac{4^{n}}{\sqrt{n}}$

[labuladong]

@michael728 感谢指出~ 已修复

[tuchao1996]

好文章，点赞

[Feyl]

Java版本：

class Solution {
    List<String> res;

    public List<String> generateParenthesis(int n) {
        res = new ArrayList<>();
        backtrack(new StringBuilder(),n,n);
        return res;
    }

    private void backtrack(StringBuilder sb,int cntl,int cntr){
        if(cntr<cntl) return;
        if(cntl<0||cntr<0) return;

        if(cntl==0&&cntr==0){
            res.add(sb.toString());
            return;
        }

        sb.append('(');
        backtrack(sb,cntl-1,cntr);
        sb.deleteCharAt(sb.length()-1);

        sb.append(')');
        backtrack(sb,cntl,cntr-1);
        sb.deleteCharAt(sb.length()-1);
    }
}

[Warning-doid]

关于回溯算法技巧的一个疑惑：如果满足结束条件，就把track加入result，有的时候需要在这里取消选择，有的时候又不需要？

[diandengpao]

我觉得作者表述有误，叶子节点是没有选择的节点，没有选择何谈选择。即在回溯中，碰到没有选择的节点即可直接回归。
作者说的更是在树中，因为在树中碰到叶子节点还是会往下递归，但在回溯中可不必。

[z1ggy-o]

@Warning-doid 看你怎么传递参数。所谓回溯，就是我们想要状态不变。如果用 pass-by-value 的形式来传参，数据本身是复制了，所以不用显式的撤回。如果是将共享的数据传，像例子里的 reference，就要显式的来回撤。

[labuladong]

对于 @Warning-doid 的问题，@z1ggy-o 你其实没说到点子上，准确来说，关键是看你结束递归的 base case。

如果 base case 在叶子节点上结束，因为叶子结点也是一个节点，所以 base case 里面也要进行「选择」和「撤销选择」。

如果 base case 在空节点上结束，那就不用考虑这些，直接 return 就好。

[ghost]

请问这道题为什么不需要for来确定位置呢

[ErronZrz]

class Solution {
    private List<String> all = new LinkedList<>();

    public List<String> generateParenthesis(int n) {
        backtrack("", n, n);
        return all;
    }

    private void backtrack(String now, int l, int r){
        if(l+r==0){
            all.add(now);
            return;
        }
        if(l>0) backtrack(now+'(', l-1, r);
        if(l<r) backtrack(now+')', l, r-1);
    }
}

写了一个更轻快的版本，其中l和r分别代表还需要的左右括号数量

[Rayso777]

想问一下，为什么先放了左括号再撤销，然后再放右括号，再撤销，这一块没太理解，哪位大佬能给解释一下？小白抱头.

[shiboys]

你是没有看过回溯的框架吧？

[llf2586]

这是已经不是多叉树了是吧

[taojiangcb]

这个 怎么不按框架套路出牌，去掉了 for 我差点又进入脑补压栈了，还好跳出来了。

[lee666-lee]

@Rayso777 你好，我也是小白，但我这样理解的，希望能帮到你。实质这就是在穷举呀。回溯算法的思路就是：1.算法过程中穷举所有组合（满足题目条件的组合/不满足题目条件的组合）；2.从所有组合中排除不满足条件的组合，最后得到满足条件的组合。放到这道题具体而言：1.在此位置先放左括号，进行backTrack递归，就相当于以左括号为根节点生成一棵子多叉树，当走到if(left==0&&right==0)时就可以记录下“正确的组合”，否则在if(left>right)和if(left<0||right<0)就返回了。2.撤销左括号，意思就是这棵子多叉树已经走完了，下面准备再试试在此位置放置右括号会有哪些“正确的组合”。3.右括号同理。

[zhongweiLeex]

简单记录一下java版本

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        backTrack(n,n,result,sb);
        return result;

    }
    private void backTrack(int leftCount,int rightCount,List<String> result,StringBuilder sb){
        //如果左括号剩下的多 说明不符合要求
        if(leftCount > rightCount) return;
        //括号数量最后 变成了 负数 不合法
        if(leftCount < 0 || rightCount < 0) return;

        if(leftCount == 0 && rightCount == 0){
            result.add(sb.toString());//找到一种可能 将结果加入到result集合中
        }

        sb.append('(');
        backTrack(leftCount-1,rightCount,result,sb);
        sb.deleteCharAt(sb.length()-1);

        sb.append(')');
        backTrack(leftCount,rightCount-1,result,sb);
        sb.deleteCharAt(sb.length()-1);
    }
}

[cheng-miao]

nice

[zhongweiLeex]

简单记录一下java版本

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        backTrack(n,n,result,sb);
        return result;

    }
    private void backTrack(int leftCount,int rightCount,List<String> result,StringBuilder sb){
        //如果左括号剩下的多 说明不符合要求
        if(leftCount > rightCount) return;
        //括号数量最后 变成了 负数 不合法
        if(leftCount < 0 || rightCount < 0) return;

        if(leftCount == 0 && rightCount == 0){
            result.add(sb.toString());//找到一种可能 将结果加入到result集合中
        }

        sb.append('(');
        backTrack(leftCount-1,rightCount,result,sb);
        sb.deleteCharAt(sb.length()-1);

        sb.append(')');
        backTrack(leftCount,rightCount-1,result,sb);
        sb.deleteCharAt(sb.length()-1);
    }
}

二刷补充说明，此处 为什么 eftCount > rightCount 就不符合要求了呢？因为题目中要想成对出现 ，左括号剩余数量始终要小于等于右括号剩余数量的，因为给出的例子中，左括号无非与右括号成对了或者左括号还没成对，那剩余的右括号就多了或者与左括号剩余相等的。

[xlintime]

js版本

/**
 * @param {number} n
 * @return {string[]}
 */

 /**
 解题思路
 1. 使用回溯算法，相当于生成一颗树
 
 
 
  */
var generateParenthesis = function(n) {
    let res=[]
    let track=[];
    // left 括号数有n个， right 括号数也有n个
    function backtrack(left,right,track){
        if(left>right){ // 因为先消费的左边的，所以一定是左边的元素比右边的少
            return ;
        }
        if(left<0||right<0){
            return 
        }
        if(left===0&&right===0){
            res.push(track.slice().join(""));
            return 
        }
        
        track.push("(");
        backtrack(left-1,right,track);// 消耗了一个左括号
        track.pop();

        track.push(")");
        backtrack(left,right-1,track); // 消耗了一个右括号
        track.pop();
    }

   backtrack(n,n,track);
   
   return res
};

[Tallminsome]

记录一下，利用的是之前排列组合的思想解题，利用的是排列 元素可重不可重选，之前做的时候误用了组合的思路导致不对，其实后面想来用组合的话不就是2n选2n个，那就只有一种情况，显然不符合题意

class Solution {
    List<String> res = new LinkedList<>();
    StringBuffer track = new StringBuffer();
    int trackSum = 0;
    boolean[] used; 
    public List<String> generateParenthesis(int n) {
        //把"("看作1
        //把")"看作-1
        //每次放进去需判断sum >= 0 不然不对，肯定是'('先于')'
        //相当于组合加上个TrackSum
        int[] nums = new int[2*n];
        used = new boolean[2 * n];
        //存放括号代表的int值，前n个是1(左括号)，后n个是-1(右括号)
        for(int i = 0; i < n; i++){
            nums[i] = 1;
            nums[i + n] = -1;
        }
        backtrack(nums,trackSum);
        return res;
    }
    //排列 元素可重不可重复选
    void backtrack(int[] nums, int trackSum){
        if(nums.length == track.length()){
            res.add(new String(track));
            trackSum = 0;
            return;
        }
        for(int i = 0; i < nums.length; i++){
            //剪枝
            if(used[i]){
                continue;
            }
            if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }
            if(trackSum + nums[i] < 0){
                //保证trackSum一直 >=0，也就是左括号比右括号数量多
                //小于0就不用append这一次
                continue;
            }
            //做选择
            if(nums[i] == 1){
                track.append('(');
            }else{
                track.append(')');
            }
            used[i] = true;
            trackSum += nums[i];
            //递归
            backtrack(nums, trackSum);
            //撤销选择
            used[i] = false;
            track.deleteCharAt(track.length() - 1);
            trackSum -= nums[i];
        }
    }
}

[bert82503]

打卡，感谢！

[bert82503]

Java版，使用LinkedList<Character>作为track，充分发挥双端队列优势，个人感觉比StringBuilder更容易理解和记忆。

class Solution {
    public List<String> generateParenthesis(int n) {
        // 可用的左括号和右括号数量初始化为 n
        backtrack(n, n);
        return res;
    }

    // 记录所有合法的括号组合
    List<String> res = new LinkedList<>();
    // 记录回溯的路径
    LinkedList<Character> track = new LinkedList<>();

    // 可用的左括号数量为 left 个，可用的右括号数量为 right 个
    void backtrack(int left, int right) {
        // 若左括号剩下的多，说明不合法
        if (left > right) {
            return;
        }
        // 数量小于 0 肯定是不合法的
        if (left < 0 || right < 0) {
            return;
        }
        // 当所有括号都恰好用完时，得到一个合法的括号组合
        if (left == 0 && right == 0) {
            res.add(applyAsString(track));
            return;
        }

        // 尝试放一个左括号
        // 做选择
        track.addLast('(');
        // 递归下一层回溯树
        backtrack(left - 1, right);
        // 撤销选择
        track.removeLast();

        // 尝试放一个右括号
        // 做选择
        track.addLast(')');
        // 递归下一层回溯树
        backtrack(left, right - 1);
        // 撤销选择
        track.removeLast();
    }

    String applyAsString(LinkedList<Character> track) {
        StringBuilder sb = new StringBuilder(track.size());
        for (Character ch : track) {
            sb.append(ch);
        }
        return sb.toString();
    }
}

[lhcezx]

贴一个C++双百版本，并且带for循环便于理解。实际上这里的for循环是可以省略的，因为同一个位置上只有两种情况: 左括号和右括号。前面带for循环是因为同一个位置的情况有k种，这里可以直接手写出来所以就省略for了

class Solution {
    vector<string> res;
    vector<char> dir {'(', ')'};
public:
    void backtrack(int n, int left, int right, string& onPath) {        //  放n个括号，代表左括号有n个，右括号也有n个，这样才合法。并且在每个位置i时，[0, i]中左括号的总数一定大于右括号的数量
        if (left < 0 || right < 0) return;
        if (right < left) return;                                       //  如果右括号放的比左括号多，则不合法，返回
        if (left == 0 && right == 0) {
            res.push_back(onPath);
            return;
        }
        for (auto a: dir) {
            onPath.push_back(a);
            if (a == '(') {
                backtrack(n, left - 1, right, onPath);
            } else {
                backtrack(n, left, right - 1, onPath);
            }
            onPath.pop_back();
        }
    }

    vector<string> generateParenthesis(int n) {
        string onPath = "";
        backtrack(n, n, n, onPath);
        return res;
    }
};

[6VastUniverse]

我是这么想的：每一次插入一对括号，这样绝对能成功，但是可能重复，所以我用set去重。时间复杂度也很大，应该是O(n^n)。

class Solution {
public:
    set <string> ans;
    vector <string> a;
    set <string> f[10] = {};

    void dfs(string a, int n)
    {
        if (n == 0)
        {
            // ans.insert(a);
            this -> a.push_back(a);
            return;
        }
        if (a == "")
        {
            dfs("()", n - 1);
            return;
        }
        for (int i = 0; i < a.size(); i ++)
        {
            string temp = a.substr(0, i + 1);
            temp += "()";
            temp += a.substr(i + 1, a.size());
            if (f[n].count(temp))
            {
                continue;
            }
            f[n].insert(temp);
            dfs(temp, n - 1);
        }
    }

    vector<string> generateParenthesis(int n)
    {
        dfs("", n);
        // vector <string> ans;
        // for (auto i = this -> ans.begin(); i != this -> ans.end(); i ++)
        // {
        //     ans.push_back(* i);
        // }
        // return ans;
        return a;
    }
};

[6VastUniverse]

哦，刚刚的好像是另一个思路，就是用set[]让每一步都不会重复，空间复杂度大，这才是那个set去重的版本：

class Solution {
public:
    set <string> ans;
    vector <string> a;
    set <string> f[10] = {};

    void dfs(string a, int n)
    {
        if (n == 0)
        {
            // ans.insert(a);
            this -> a.push_back(a);
            return;
        }
        if (a == "")
        {
            dfs("()", n - 1);
            return;
        }
        for (int i = 0; i < a.size(); i ++)
        {
            string temp = a.substr(0, i + 1);
            temp += "()";
            temp += a.substr(i + 1, a.size());
            if (f[n].count(temp))
            {
                continue;
            }
            f[n].insert(temp);
            dfs(temp, n - 1);
        }
    }

    vector<string> generateParenthesis(int n)
    {
        dfs("", n);
        // vector <string> ans;
        // for (auto i = this -> ans.begin(); i != this -> ans.end(); i ++)
        // {
        //     ans.push_back(* i);
        // }
        // return ans;
        return a;
    }
};

[zhongweiLeex]

使用括号数量递增

class Solution {
    List<String> result = new LinkedList<>();
    public List<String> generateParenthesis(int n) {
        dfs(0,0,n,new StringBuilder());
        return result;
    }
    private void dfs(int left , int right , int n,StringBuilder sb){
        if(right > left) return;
        if(left > n || right > n) return;
        if(left == n && right == n){
            result.add(sb.toString());
            return;
        }
        sb.append('(');
        dfs(left+1,right,n,sb);
        sb.deleteCharAt(sb.length()-1);

        sb.append(')');
        dfs(left,right+1,n,sb);
        sb.deleteCharAt(sb.length()-1);
    }
}

[yonggui-yan]

daka

left， right 作为输入，表示左右还可用的括号数。

[lambdaxing]

可以在递归生成括号的过程中用一个 int 变量 val 记录左右括号的个数，左括号减1，右括号加1。当 val 小于 0 时说明此时 ')' 的个数大于 '(' 的个数，不合法；当 val 等于 0 时只能添加左括号（添加右括号也无妨，会在下一层递归判为不合法）；当 val 大于 0 时左右括号都可添加。最后通过 track 的长度与 val 的值来判断是否合法：

class Solution {
public:

    void backtrack(int val, string& track, vector<string>& res, int tracklen) {
        if(val < 0) return;
        if(track.length() == tracklen) {
            if(val == 0)
                res.push_back(track);
            return;
        }

        track.push_back('(');
        val++;
        backtrack(val, track, res, tracklen);
        val--;
        track.pop_back();

        track.push_back(')');
        val--;
        backtrack(val, track, res, tracklen);
        val++;
        track.pop_back();
    }

    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string track;
        backtrack(0, track, res, 2 * n);
        return res;
    }
};

[lambdaxing]

写错了，是左括号加1，右括号减1。

[WeiLong-Zh]

class Solution {
    // 存放结果
    List<String> results = new ArrayList<>();
    // 存放一条路径上的值
    List<Character> path = new ArrayList<>();
    int left = 0;  // 记录左括号的个数
    int right = 0; // 记录右括号的个数
    public void backTracking(int curDepth,int targetDepth){
        if (curDepth == targetDepth){
            if (left == right){
                StringBuilder sb = new StringBuilder();
                for (Character c: path)
                    sb.append(c);
                results.add(new String(sb));
            }
            return;
        }
        // 放左括号
        // 剪枝 满足条件才放入
        if (left + 1 >= right){
            left++;
            path.add('(');
            backTracking(curDepth + 1,targetDepth);
            left--;
            path.remove(path.size() - 1);
        }
        if (right + 1 <= left){
            right++;
            path.add(')');
            backTracking(curDepth + 1,targetDepth);
            right--;
            path.remove(path.size() - 1);
        }
    }
    public List<String> generateParenthesis(int n) {
        backTracking(0,2 * n);
        return results;
    }
}

[mangohow]

剪个枝，go版本

func generateParenthesis(n int) []string {
	res := make([]string, 0)

	track := make([]byte, 0)
	// i,j分别表示'('和')'已经放置的数量
	var backtrack func(i, j int)
	backtrack = func(i, j int) {
		if i == n && j == n {
			res = append(res, string(track))
			return
		}

		// 选择'('
		if i != n {
			track = append(track, '(')
			backtrack(i+1, j)
			track = track[:len(track)-1]
		}
		// 前面'('的数量必须大于')'的数量才能选择')'
		if i > j {
			track = append(track, ')')
			backtrack(i, j+1)
			track = track[:len(track)-1]
		}
	}

	backtrack(0, 0)

	return res
}