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

Have you met this question in a real interview?

Yes

Example

Givenn = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

1. at any given time if leftN (number of "(" ) in string needs to be greater than rightN (number of ")") in string

2. if leftN less than n, we can keep adding "("

can implement using seperate backtracking for both "(" and ")"

public class Solution {
    /*
     * @param n: n pairs
     * @return: All combinations of well-formed parentheses
     */
    public List<String> generateParenthesis(int n) {
        // write your code here
        List<String> ans = new ArrayList<>();
        String cur = "";
        if (n == 0) {
            ans.add(cur);
            return ans;
        }

        int leftN = 0;
        int rightN = 0;


        dfs(leftN, rightN, n, cur, ans);
        return ans;
    }

    //((()))
    //1.left N must greater right N at any given time
    //2.if left N < n, then we can keep insert N
    public void dfs(int leftN, int rightN, int n, String cur, List<String> ans) {

        //exit
        if (leftN == n && rightN == n) {
            ans.add(new String(cur));
            return;
        }

        if (leftN < n) {
            cur += "(";
            dfs(leftN + 1, rightN, n, cur, ans);
            cur = cur.substring(0, cur.length() - 1);
        }

        if (rightN < leftN) {
            cur += ")";
            dfs(leftN, rightN + 1, n, cur, ans);
            cur = cur.substring(0, cur.length() - 1);
        }


    }
}