Start learning free

LESSON 267 OF 347 · BACKTRACKING

Generate Parentheses in C#: Backtracking with Pruning

Practice O(2^n) Read the full explanation

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

A parentheses string is well-formed if and only if:

  • It is the empty string, or

  • It can be written as AB (A concatenated with B), where A and B are well-formed, or

  • It can be written as (A), where A is well-formed.


Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Note: 1 <= n <= 8


STEP 1 OF 10
    Ctrl + Enter to check

    C# · BACKTRACKING

    Generate Parentheses in C#, explained

    Problem overview

    The method GenerateParentheses receives an integer n, the number of pairs of parentheses, and must return every well-formed string that uses exactly n pairs, as a List<string>. A string is well-formed when every ( is closed by a matching ) that comes later, so no prefix ever contains more closing parentheses than opening ones, and the totals match at the end.

    For n = 3 the answer is "((()))", "(()())", "(())()", "()(())" and "()()()". For n = 1 it is just "()". The lesson's limit is 1 <= n <= 8.

    Approach: build the string one character at a time

    A string with n pairs has length 2 * n, and each position holds either ( or ). Trying all 2^(2n) combinations and testing each would waste almost all the work. The better idea is to build the string from left to right and abandon a prefix as soon as it can no longer become a well-formed string. That is backtracking with pruning.

    The recursion carries its whole state in its parameters: the string built so far, the target length, how many ( it holds (open) and how many ) (closed). Two rules throw a prefix away:

    • Too many closing parentheses. If closed exceeds open, the prefix has a ) with nothing to close, and appending more characters can't fix that.
    • Too many opening parentheses. Every unclosed ( needs a ) later. If open - closed is larger than the number of positions left, there isn't enough room to close them all.

    A string that reaches the full length without being pruned is well-formed, so it goes into the result. Otherwise, the recursion branches twice: one call appends ( and the other appends ).

    Take n = 1, so the target length is 2. The empty string branches into "(" and ")". The prefix ")" has one closing parenthesis and no opening one, so it is pruned. The prefix "(" branches into "((", which is pruned because the two openings can't both be closed within the length, and "()", which reaches the full length and is stored.

    Step by step

    1. Add a field of type List<string> named solutions above GenerateParentheses, so the recursive helper can add results without passing a list through every call.
    2. Reset it on every call. GenerateParentheses assigns a fresh empty list first, so results from an earlier call can't leak into this one.
    3. Start the search with an empty string, a target length of 2 * n and both counters at 0.
    4. Return solutions when the search is done.
    5. Declare Generate. It is a public void helper with the parameters current, n, open and closed. Inside it, n is the full string length, twice the number of pairs.
    6. Prune closings. Return when open < closed.
    7. Prune openings. Return when open > closed + (n - current.Length + 1), which is the check that too many parentheses are still waiting to be closed.
    8. Store complete strings. When current.Length == n, add the string to solutions and return. A full-length string that survived both prunes is balanced.
    9. Branch on (. Recurse with a ( appended and open increased by one.
    10. Branch on ). Recurse with a ) appended and closed increased by one.

    The solution in C#

    class Solution {
    public void Generate(string current, int n, int open, int closed) {
        if (open < closed) {
            return;
        }
        if (open > closed + (n - current.Length + 1)) {
            return;
        }
        if (current.Length == n) {
            solutions.Add(current);
            return;
        }
        Generate(current + '(', n, open + 1, closed);
        Generate(current + ')', n, open, closed + 1);
    }

    List<string> solutions;
    public List<string> GenerateParentheses(int n) {
        solutions = new();
        Generate("", 2 * n, 0, 0);
        return solutions;
    }
}

    The C# details worth a closer look:

    • Strings are immutable. current + '(' doesn't modify current; it builds a new string. Each recursive call therefore receives its own prefix, and nothing needs to be undone after the call returns. That is why this backtracking has no "remove the last character" step.
    • String plus char. When one operand is a string, + appends the character as text: "(" + '(' is "((". Without a string operand it behaves differently: 'a' + 'b' adds the character codes and gives the integer 195. Starting from "" keeps every + a string concatenation.
    • Target-typed new(). In solutions = new(); the compiler takes the type from the field, which is List<string>. It is shorthand for new List<string>() and is available in current C#.
    • Length is a property. Strings use Length, without parentheses, while a List uses Count.
    • Why the + 1 doesn't change the result. The difference open - closed and the number of remaining positions always have the same parity, since the total target length is even. The surplus can therefore never be exactly one more than the remaining positions, and the check behaves like open - closed > remaining.

    Complexity

    Time: proportional to the number of results. The number of well-formed strings with n pairs is the Catalan number: 1, 2, 5, 14, 42, 132, 429 and 1430 for n from 1 to 8. Both prunes together mean that every prefix the search keeps can still be completed into a well-formed string, so the recursion creates few wasted branches. Each result costs a string of length 2n to build, which gives roughly O(n * C(n)) work, where C(n) is the Catalan number. That growth is close to 4^n, so n has to stay small, and the limit of 8 does.

    Space: O(n) besides the output. The recursion is 2n calls deep, and each level holds one prefix of up to 2n characters.

    Edge cases and common mistakes

    • Order of the results. Trying ( before ) gives the strings in the order shown in the example, starting with "((()))" and ending with "()()()".
    • Confusing n in the helper. In Generate, n is the length 2 * n, not the number of pairs. Passing the number of pairs would produce strings that are too short.
    • Not resetting solutions. If the field is created only once, a second call returns the strings from the first call as well.
    • Checking only at the end. Generating all strings and filtering them still gives correct results, but visits 2^(2n) strings. Pruning cuts almost all of them.
    • Allowing a closing parenthesis too early. A string such as "())(" has equal counts but is not well-formed. The open < closed check applies at every prefix, which is what rules it out.
    • Using char addition by accident. Writing a character-only expression such as '(' + ')' yields an integer, not a string.

    Testing

    • n = 1 gives "()".
    • n = 2 gives "(())" and "()()".
    • n = 3 gives the five strings listed above.
    • n = 8 gives 1430 strings.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free