Question

剑指 Offer II 085. 生成匹配的括号

题目描述

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

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

 

提示：

• 1 <= n <= 8

 

注意：本题与主站 22 题相同： https://leetcode.cn/problems/generate-parentheses/

解法

方法一

class Solution:
  def generateParenthesis(self, n: int) -> List[str]:
    def dfs(left, right, t):
      if left == n and right == n:
        ans.append(t)
        return
      if left < n:
        dfs(left + 1, right, t + '(')
      if right < left:
        dfs(left, right + 1, t + ')')

    ans = []
    dfs(0, 0, '')
    return ans

class Solution {
  public List<String> generateParenthesis(int n) {
    List<String> ans = new ArrayList<>();
    dfs(0, 0, n, "", ans);
    return ans;
  }

  private void dfs(int left, int right, int n, String t, List<String> ans) {
    if (left == n && right == n) {
      ans.add(t);
      return;
    }
    if (left < n) {
      dfs(left + 1, right, n, t + "(", ans);
    }
    if (right < left) {
      dfs(left, right + 1, n, t + ")", ans);
    }
  }
}

class Solution {
public:
  vector<string> generateParenthesis(int n) {
    vector<string> ans;
    dfs(0, 0, n, "", ans);
    return ans;
  }

  void dfs(int left, int right, int n, string t, vector<string>& ans) {
    if (left == n && right == n) {
      ans.push_back(t);
      return;
    }
    if (left < n) dfs(left + 1, right, n, t + "(", ans);
    if (right < left) dfs(left, right + 1, n, t + ")", ans);
  }
};

func generateParenthesis(n int) []string {
  var ans []string
  var dfs func(left, right int, t string)
  dfs = func(left, right int, t string) {
    if left == n && right == n {
      ans = append(ans, t)
      return
    }
    if left < n {
      dfs(left+1, right, t+"(")
    }
    if right < left {
      dfs(left, right+1, t+")")
    }
  }
  dfs(0, 0, "")
  return ans
}

function generateParenthesis(n: number): string[] {
  let ans = [];
  let dfs = function (left, right, t) {
    if (left == n && right == n) {
      ans.push(t);
      return;
    }
    if (left < n) {
      dfs(left + 1, right, t + '(');
    }
    if (right < left) {
      dfs(left, right + 1, t + ')');
    }
  };
  dfs(0, 0, '');
  return ans;
}

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  let ans = [];
  let dfs = function (left, right, t) {
    if (left == n && right == n) {
      ans.push(t);
      return;
    }
    if (left < n) {
      dfs(left + 1, right, t + '(');
    }
    if (right < left) {
      dfs(left, right + 1, t + ')');
    }
  };
  dfs(0, 0, '');
  return ans;
};