Start learning free

LESSON 292 OF 414 · BACKTRACKING

Generate Parentheses in Scala: Pruned Backtracking

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

    SCALA · BACKTRACKING

    Generate Parentheses in Scala, explained

    Problem overview

    The method generateParentheses receives an integer n, from 1 to 8, and returns a List[String] with every well-formed string made of n pairs of parentheses. A string is well-formed when every ( is closed by a later ) and no prefix closes more than it has opened.

    For n = 3 the answer is the five strings ((())), (()()), (())(), ()(()) and ()()(). For n = 1 it is just ().

    Approach: build the string one character at a time

    A string with n pairs has 2n characters, each either ( or ). Trying all 4 to the power n combinations and filtering the valid ones wastes most of the effort. Instead, build the string left to right and give up on a prefix as soon as it cannot lead to a valid result. Two facts make that possible.

    • Closing too early. If a prefix contains more ) than (, some parenthesis closes something that was never opened, and no later characters can repair that. Stop.
    • Opening too many. If the prefix has more unclosed ( than there are positions left, it can never be balanced. Stop.

    A prefix that passes both checks is extended with ( and with ), two recursive calls. When the length reaches 2n, the string has survived both checks and is guaranteed to be balanced, so it is saved.

    Step by step

    1. Declare a shared buffer. A field var solutions: ArrayBuffer[String] = null lets the recursive helper collect results without returning them.
    2. Reset it in generateParentheses with a fresh ArrayBuffer[String](), so strings from earlier calls can't remain.
    3. Start the search with an empty string, the target length 2 * n and both counters at 0.
    4. Return solutions.toList, because the method promises an immutable List[String].
    5. Declare generate(current, n, open, closed) returning Unit. Inside the helper, n is the full length of the string, twice the number of pairs. open and closed count the parentheses of each kind in current.
    6. First prune: return when open < closed, because the prefix closed more than it opened.
    7. Second prune: return when open > closed + (n - current.length + 1). The slots left are n - current.length, and even if all of them are ), closed grows by at most that much.
    8. Complete string: when current.length == n, append it with solutions += current and return.
    9. Extend both ways: recurse with current + "(" and open + 1, then with current + ")" and closed + 1.

    The solution in Scala

    class Solution {
    def generate(current: String, n: Int, open: Int, closed: Int): Unit = {
        if (open < closed) {
            return
        }
        if (open > closed + (n - current.length + 1)) {
            return
        }
        if (current.length == n) {
            solutions += current
            return
        }
        generate(current + "(", n, open + 1, closed)
        generate(current + ")", n, open, closed + 1)
    }

    var solutions: ArrayBuffer[String] = null
    def generateParentheses(n: Int): List[String] = {
        solutions = ArrayBuffer[String]()
        generate("", 2 * n, 0, 0)
        solutions.toList
    }
}

    Scala details:

    • The type ArrayBuffer. It is a growable array from scala.collection.mutable. A file of your own needs import scala.collection.mutable.ArrayBuffer.
    • String building. Strings are immutable, so current + "(" creates a new string and leaves current untouched. That is why each branch of the recursion keeps its own prefix and no undo step is needed.
    • += on a buffer appends an element. solutions += current changes the buffer in place.
    • toList copies the buffer into an immutable List, the declared return type. It is the last expression, so no return is needed.
    • The field is shared. solutions belongs to the Solution object and is replaced at the start of every call to generateParentheses.
    • The + 1 in the second prune. It never changes the outcome. The numbers of ( and ) in a prefix add up to its length, so open - closed has the same parity as the length, and so as the number of slots left (the total length is even). The surplus can therefore never be exactly one more than the slots left.

    Complexity

    Time. The number of results is the n-th Catalan number: 1, 2, 5, 14, 42, 132, 429 and 1430 for n from 1 to 8. The pruning keeps the search close to that number. For n = 3, generate is called 35 times, against 127 for the full tree of all (/) choices. For n = 8 it is called 10,975 times, against 131,071. Each call builds a string of up to 2n characters, so the work is on the order of the number of results times n, which grows roughly like 4 to the power n divided by a power of n.

    Space. The recursion is at most 2n + 1 calls deep. The stored strings take most of the memory, because there are Catalan(n) of them with 2n characters each.

    Edge cases and common mistakes

    • n = 1. The only result is ().
    • Result order. The search tries ( before ), so the results come out in alphabetical order with ( first, as in the n = 3 list above.
    • Counts. The result lengths for n from 1 to 8 are 1, 2, 5, 14, 42, 132, 429 and 1430.
    • Not resetting the buffer. If solutions isn't replaced at the start of each call, a second call returns its results appended to the first call's.
    • Confusing n in the helper. The helper's n is the string length, 2 * pairs. Passing the number of pairs would make the search stop at strings of half the right length.
    • Checking only at the end. Generating all strings and testing each one at the end is correct but explores far more.
    • Counting wrong. Equal numbers of ( and ) are not enough: )( has one of each but isn't well-formed. That is why the first prune watches every prefix.

    Testing

    • n = 1 gives List("()").
    • n = 3 gives List("((()))", "(()())", "(())()", "()(())", "()()()").
    • n = 4 gives 14 strings, and n = 8 gives 1430.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free