L22. Generate Parentheses

backtrack

Problem:

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:

• only add '(' or ')' when we know it will remain a valid sequence. We can do this by keeping track of the number of opening and closing brackets we have placed so far.

• We can start an opening bracket if we still have one (of n) left to place. And we can start a closing bracket if it would not exceed the number of opening brackets.

public List<String> generateParentheses(int n){
    List<String> ans = new ArrayList<>();
    backtrack(ans, "", 0,0,n);
    return ans;
}
public void backtrack(List<String> ans, String str, int left , int right, int n){
    if(n <= 0) return;
    if(str.length() == n*2){
        ans.add(str);
        return;
    }
    if(left < n){
        backtrack(ans, str + '(', left+1, right, n);
    }
    if(right < left){
        backtrack(ans, str + ")", left, right + 1, n);
    }
}