22. Generate Parentheses (Medium)

https://leetcode.com/problems/generate-parentheses/

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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solutions

class Solution {

    // To form a valid parentheses pattern,  the open parentheses must be equal or more than close parentheses
    // during the process of generating the combination.

    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        if (n == 0) {
            return ans;
        }

        if (n == 1) {
            ans.add("()");

            return ans;
        }

        Stack<String> track = new Stack<>();

        recurse(n, n, track, ans);

        return ans;
    }

    private void recurse(int openP, int closeP, Stack<String> track, List<String> ans) {
        // openP represents how many open parentheses left, closeP is the close parentheses that left.

        if (openP < 0 || closeP < 0) {
            return;
        }

        // all the left and right parentheses are used up.
        if (openP == 0 && closeP == 0) {
            String s = "";
            for (int i = 0; i < track.size(); i++) {
                s += track.get(i);
            }

            ans.add(s);

            return;
        }

        // add open parentheses first
        track.push("(");
        recurse(openP - 1, closeP, track, ans);
        track.pop();

        // append close parentheses thereafter
       if (openP < closeP) {
            track.push(")");
            recurse(openP, closeP - 1, track, ans);
            track.pop();
        }
    }
}

Incorrect Solutions

References