22. Generate Parentheses

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }
    private void backtrack(List<String> result, StringBuilder sb, int open, int close, int n) {
        if (sb.length() == 2 * n) {
            result.add(sb.toString());
            return;
        }
        if (open < n) {
            sb.append('(');
            backtrack(result, sb, open + 1, close, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')');
            backtrack(result, sb, open, close + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

class Solution:
    def generateParenthesis(self, n):
        result = []

        def backtrack(sb, open_count, close_count):
            if len(sb) == 2 * n:
                result.append("".join(sb))
                return

            if open_count < n:
                sb.append('(')
                backtrack(sb, open_count + 1, close_count)
                sb.pop()

            if close_count < open_count:
                sb.append(')')
                backtrack(sb, open_count, close_count + 1)
                sb.pop()

        backtrack([], 0, 0)
        return result

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string sb;

        backtrack(result, sb, 0, 0, n);

        return result;
    }

private:
    void backtrack(vector<string>& result, string& sb,
                   int open, int close, int n) {
        if (sb.length() == 2 * n) {
            result.push_back(sb);
            return;
        }

        if (open < n) {
            sb.push_back('(');
            backtrack(result, sb, open + 1, close, n);
            sb.pop_back();
        }

        if (close < open) {
            sb.push_back(')');
            backtrack(result, sb, open, close + 1, n);
            sb.pop_back();
        }
    }
};

var generateParenthesis = function(n) {
    const result = [];
    const sb = [];

    function backtrack(open, close) {
        if (sb.length === 2 * n) {
            result.push(sb.join(''));
            return;
        }

        if (open < n) {
            sb.push('(');
            backtrack(open + 1, close);
            sb.pop();
        }

        if (close < open) {
            sb.push(')');
            backtrack(open, close + 1);
            sb.pop();
        }
    }

    backtrack(0, 0);
    return result;
};