LeetCode：22. Generate Parentheses（Medium）

1. 原题链接

https://leetcode.com/problems/generate-parentheses/description/

2. 题目要求

给出一个正整数n，请求出由n对合法的圆括号组合

例如，n = 3，答案：

3. 解题思路

采用递归的方法：给定的整数为n，定义一个字符串类型变量str用来保存组合。"("的个数记为left，")"的个数记为right，当left<n时或者right<left时都进行递归。

当str的长度length==2*n时，说明该组合已由n对圆括号组成，返回。

4. 代码实现

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses22 {
    public static void main(String[] args) {
        List<String> res = new ArrayList<>();
        res = GenerateParentheses22.generateParenthesis(4);
        for (String s : res)
            System.out.println(s);
    }

    public static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, "", 0, 0, n);
        return res;

    }

    public static void backtrack(List<String> res, String str, int left, int right, int n) {
        if (str.length() == n * 2) {
            res.add(str);
            return; // 直接跳出该次递归
        }

        if (left < n)
            backtrack(res, str + "(", left + 1, right, n);
        if (right < left)
            backtrack(res, str + ")", left, right + 1, n);
    }
}

　运行结果：

 2017-12-27 09:47:49