LeetCode 22. Generate Parentheses

22. Generate Parentheses

Difficulty: Medium

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

Language: Java

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        dfsHelper(n, result, new char[n * 2], 0, 0);
        return result;
    }
    
    private void dfsHelper(int n, List<String> result, char[] chars, int index, int p) {
        if (p < 0 || p > n) {
            return;
        }
        if (index == chars.length) {
            if (p == 0) {
                result.add(new String(chars));
            }
            return;
        }
        chars[index] = '(';
        dfsHelper(n, result, chars, index + 1, p + 1);
        chars[index] = ')';
        dfsHelper(n, result, chars, index + 1, p - 1);
        
    }
}