题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1
输出：[“()”]

提示：

• 1 <= n <= 8

解法

暴力解法

JavaScript

暴力解法链接

var generateParenthesis = function (n) {
    let set = new Set(['()']);
    for (let c = 2; c <= n; c++) {
        let nextSet = new Set();
        for (const s of set) {
            for (let j = 0; j <= s.length; j++) {
                nextSet.add(s.slice(0, j) + '()' + s.slice(j));
            }
        }
        set = nextSet;
    }
    return [...set];
};

Java

class Solution {
    public List<String> generateParenthesis(int n) {
        if (n == 1) {
            return Arrays.asList("()");
        }
        Set<String> hs = new HashSet<>();
        for (String s : generateParenthesis(n-1)) {
            for (int i = 0; i < 2*n-2; i++) {
                hs.add(s.substring(0,i) + "()" + s.substring(i,s.length()));
            }
        }
        return new ArrayList(hs);
    }
}

dfs

JavaScript

/*
 * @lc app=leetcode.cn id=22 lang=javascript
 *
 * [22] 括号生成
 */
// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  let result = [];
  dfs('', n, n, result);
  return result;
};
function dfs(str, left, right, result) {
  if (left === 0 && right === 0) {
    result.push(str);
    return;
  }
  if (right < left) {
    return;
  }
  if (left !== 0) {
    dfs(str + '(', left - 1, right, result);
  }
  if (right !== 0) {
    dfs(str + ')', left, right - 1, result)
  }
}
// @lc code=end

Java

class Solution {
    List<String> list=new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if (n<1||n>8){
            return null;
        }
        def("",0,0,n);
        return list;
    }
    public void def(String paths,int left,int right,int n){
        if(left>n||right>n||right>left){
            return;
        }
        if(paths.length()==2*n){
            list.add(paths);
            return;
        }
        def(paths+"(", left+1, right, n);
        def(paths+")", left, right+1, n);
    }
}