22. Generate Parentheses.md

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

---

Solution

• mine

  • Java

    • Recursion Runtime: 1 ms, faster than 83.39%, Memory Usage: 39.3 MB, less than 21.29% of Java online submissions

      public List<String> generateParenthesis(int n) {
          List<String> res = new ArrayList<>();
          generateParenthesis("", n, n, res);
          return res;
      }
      
      public void generateParenthesis(String pre, int frontCount, int backCount, List<String> res) {
          if (frontCount == 0) {
              StringBuilder sb = new StringBuilder().append(pre);
              while (backCount > 0) {
                  sb.append(")");
                  backCount--;
              }
              res.add(sb.toString());
              return;
          }
          if (frontCount <= backCount) {
              generateParenthesis(pre + "(", frontCount - 1, backCount, res);
              if (frontCount != backCount) {
                  generateParenthesis(pre + ")", frontCount, backCount - 1, res);
              }
          }
      }
      

    • LinkedList Runtime: 38 ms, faster than 5.16%, Memory Usage: 39.4 MB, less than 20.64% of Java online submissions

      public List<String> generateParenthesis(int n) {
          LinkedList<String> linkedList = new LinkedList<>();
          linkedList.add("");
          while (linkedList.peek().length() != 2 * n) {
              String s = linkedList.pop();
              if (s.isEmpty()) {
                  linkedList.add("()");
              } else {
                  for (int i = 0; i < s.length(); i++) {
                      if (s.charAt(i) == '(') {
                          String t = s.substring(0, i + 1) + "()" + s.substring(i + 1);
                          if (!linkedList.contains(t)) {
                              linkedList.add(t);
                          }
                      }
                  }
                  linkedList.add(s + "()");
              }
          }
          return linkedList;
      }
      

---

• the most votes

  Backtracking Runtime: 4 ms, faster than 19.85%, Memory Usage: 41.4 MB, less than 5.16% of Java online submissions

  public List<String> generateParenthesis(int n) {
      List<String> list = new ArrayList<String>();
      backtrack(list, "", 0, 0, n);
      return list;
  }
  
  public void backtrack(List<String> list, String str, int open, int close, int max){
  
      if(str.length() == max*2){
          list.add(str);
          return;
      }
  
      if(open < max)
          backtrack(list, str+"(", open+1, close, max);
      if(close < open)
          backtrack(list, str+")", open, close+1, max);
  }
  

---

• official solution

  • Brute Force

    Runtime: 2 ms, faster than 30.06%, Memory Usage: 39.4 MB, less than 20.64% of Java online submissions

    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }
    
    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current))
                result.add(new String(current));
        } else {
            current[pos] = '(';
            generateAll(current, pos+1, result);
            current[pos] = ')';
            generateAll(current, pos+1, result);
        }
    }
    
    public boolean valid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return (balance == 0);
    }
    

  • Backtracking

    Runtime: 3 ms, faster than 24.50%, Memory Usage: 41.1 MB, less than 5.16% of Java online submissions

    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }
    
    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }
    
        if (open < max)
            backtrack(ans, cur+"(", open+1, close, max);
        if (close < open)
            backtrack(ans, cur+")", open, close+1, max);
    }
    

  • Closure Number

    Runtime: 14 ms, faster than 5.16%, Memory Usage: 43.6 MB, less than 5.16% of Java online submissions

    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c)
                for (String left: generateParenthesis(c))
                    for (String right: generateParenthesis(n-1-c))
                        ans.add("(" + left + ")" + right);
        }
        return ans;
    }