Categories
interview

Generate Parenthesis

JavaScript

/**
 * @param {number} n
 * @return {string[]}
 */
const generateParenthesis = (n) => {
  const ret = [];
  computeParenthesis(n, n, '', ret);
  return ret;
};

const computeParenthesis = (open, close, str, ret) => {
  if (close === 0) {
    return ret.push(str);
  }
  if (open > 0) {
    computeParenthesis(open - 1, close, str + '(', ret);
  }
  if (close > open) {
    computeParenthesis(open, close - 1, str + ')', ret);
  }
};

Java

class Solution {
    List<String> list;
    public List<String> generateParenthesis(int n) {
        list = new ArrayList<String>();
        genP("", n, n);
        return list;
    }
    
    public void genP(String str, int open, int close) {
        if (close == 0) {
          list.add(str);
          return;
        } 
        if (open > 0) {
          genP(str + '(', open - 1, close);
        }
        if (close > open) {
          genP(str + ')', open, close - 1);      
        }
    }
}