Back to DSA

Generate Parentheses

medium
Acceptance: 52%
BacktrackingStrings

Given an integer n, produce every arrangement of n pairs of parentheses that is syntactically balanced.

Examples

Example 1:
Input:n = 2
Output:["(())","()()"]
Example 2:
Input:n = 4
Output:["(((())))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"]

Hints

Related Problems

Valid PalindromeeasyLongest Substring Without Repeating CharactersmediumGroup AnagramsmediumLongest Palindromic SubstringmediumString to Integer (atoi)medium
00:00
import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(n, 0, 0, new StringBuilder(), result);
        return result;
    }

    private void backtrack(int n, int open, int close, StringBuilder current, List<String> result) {
        if (current.length() == 2 * n) { result.add(current.toString()); return; }
        if (open < n) { current.append('('); backtrack(n, open + 1, close, current, result); current.deleteCharAt(current.length() - 1); }
        if (close < open) { current.append(')'); backtrack(n, open, close + 1, current, result); current.deleteCharAt(current.length() - 1); }
    }
}
Time complexityO(4^n / sqrt(n))
Space complexityO(n)