Interview question: generate all valid combinations of n pairs of parentheses
Definition
So, the task at hand is the subject of a common interview question: Implement an algorithm to get all valid (opened and closed) combinations of n pairs of parentheses. This means that for n=1 there is only one solution: "()". "((" or "))" are not valid, for 2 you will have "(())" and "()()" and so on. The question is trying to test how the interviewee handles recursion and what is commonly called backtracking. But as usual, there's more than one way to skin a cat, although for the life of me I can't see why you would want to do that.
The solutions here will be in C# and the expected result is an enumeration of strings containing open and closed parentheses. The code can be easily translated into other languages, including Javascript (ECMAScript 2015 introduced iterators and generator functions), but that's left to the reader. Let's begin.
Analysis
Before we solve any problem we need to analyse it and see what are the constraints and the expected results. In this case there are several observations that can be made:
- the resulting strings will be of length n*2 (n pairs)
- they will contain n '(' characters and n ')' characters
- they cannot start with a ')' or end in a '('
- in order to generate such a string, we can start with a smaller string to which we add '(' or ')'
- we cannot add a ')' if there isn't at least one corresponding unclosed '('
- if we add a '(' we need to have enough characters left to close the parenthesis, so the number of unclosed parentheses cannot exceed the characters left to fill
- we could count the open and closed parentheses, but we only care about the number of unclosed ones, so instead of "closed" and "open" values, we can only use "open" to represent unclosed parentheses
Let's go for some variables and calculations:
- n = number of pairs
- open = number of unclosed parentheses in a string
- open cannot be negative
- one cannot add ')' if open = 0
- one cannot add '(' if open >= n*2 - substring.length
Recursive solution
A simple implementation of these requirements can done with recursion:
public IEnumerable<string> GenerateRecursive(int n, string root = "", int open = 0)
{
// substring is long enough, return it and exit
if (root.Length == n * 2)
{
yield return root;
yield break;
}
// if we can add '(' to existing substring, continue the process with the result
if (open < n * 2 - root.Length)
{
// if only C# could just 'yield IteratorFunction()' this would look sleeker
foreach (var s in GenerateRecursive(n, root + "(", open + 1))
{
yield return s;
}
}
// if we can add ')' to existing substring, continue the process with the result
if (open > 0)
{
foreach (var s in GenerateRecursive(n, root + ")", open - 1))
{
yield return s;
}
}
}
However, every time you see recursion you have to ask yourself: could n be large enough to cause a stack overflow? For example this fails for n=3000. The nice thing about this method, though, is that it can be limited to the number of items you want to see. For example var firstTen = GenerateRecursive(1000).Take(10) is very fast, as the generation is depth first and only computes the first ten values and exits.
So, can we replace the recursion with iteration?
Iterative solution
In order to do thing iteratively, we need to store the results of the previous step and use them in the current step. This means breadth first generation, which has its own problems. Let's see some code:
public IEnumerable<string> GenerateIteration(int n)
{
// using named tuples to store the unclosed parentheses count with the substring
var results = new List<(string Value,int Open)>() { ("",0) };
for (int i = 0; i < n*2; i++)
{
// each step we compute the list of new strings from the list in the previous step
var newResults = new List<(string Value, int Open)>();
foreach (var (Value, Open) in results)
{
if (Open < n * 2 - Value.Length)
{
newResults.Add((Value + "(", Open + 1));
}
if (Open > 0)
{
newResults.Add((Value + ")", Open - 1));
}
}
results = newResults;
}
return results.Select(r=>r.Value);
}It's pretty sleek, but if you try something like var firstTen = GenerateRecursive(1000).Take(10) now it will take forever since all combinations of 1000 parentheses need to be computed and stored before taking the first 10! BTW, we can write this much nicer with LINQ, but be careful at the gotcha in the comment:
public IEnumerable<string> GenerateLinq(int n)
{
// looks much nicer with LINQ
IEnumerable<(string Value, int Open)> results = new[] { ("", 0) };
for (var i = 0; i < n * 2; i++)
{
results =
results
.Where(r => r.Open < n * 2 - r.Value.Length)
.Select(r => (Value: r.Value + "(", Open: r.Open + 1))
.Concat(results
.Where(r => r.Open > 0)
.Select(r => (Value: r.Value + ")", Open: r.Open - 1))
); // but if you do not end this with a .ToList()
// it will generate a huge expression that then will be evaluated at runtime! Oops!
}
return results.Select(r => r.Value);
}But can't we do better? One is going to stack overflow, the other memory overflow and the last one kind of does both.
Incremental solution
They did say this requires an incremental solution, right? So why don't we take this literally? '(' and ')' are like 0 and 1, as ')' must always follow a '('. If you view a parenthesis string as a binary number, then all possible combinations can be encoded as numbers. This means that we could conceivably write a very fast function that would compute all possible combinations using bit operations, maybe even special processor instructions that count bits and so on. However, this would work only for n<=32 or 64 depending on the processor architecture and we don't want to get into that. But we can still use the concept!
If a string represents a fictional number, then you can start with the smallest one, increment it and check for validity. If you combine the incremental operation with the validity check you don't need to go through 2n operations to get the result. It doesn't use any memory except the current string and it is depth first generation. The best of both worlds! Let's see some code:
public IEnumerable<string> GenerateIncrement(int n)
{
// the starting point is n open parentheses and n closing ones
// we use the same array of characters to generate the strings we display
var arr = (new string('(', n) + new string(')', n)).ToCharArray();
// iteration will stop when incrementation reaches the "maximum" valid combination
var success = true;
while (success)
{
yield return new string(arr);
success = Increment(arr, n);
}
}
private bool Increment(char[] arr, int n)
{
// we begin with a valid string, which means there are no unclosed parentheses
var open = 0;
// we start from the end of the string
for (var i = arr.Length - 1; i >= 0; i--)
{
// ')' is equivalent to a 1. To "increment" this string we need to go to the previous position
// incrementing 01 in binary results in 10
if (arr[i] == ')')
{
open++;
continue;
}
// '(' is equivalent to a 0. We will turn it into a ')' to increment it,
// but only if there are unclosed parentheses to close
open--;
if (open == 0) continue;
// we 'increment' the value
arr[i] = ')';
// now we need to reset the rest of the array
var k = n - (open + i) / 2;
// as many opening parenthesis as possible
for (var j = i + 1; j < i + 1 + k; j++)
{
arr[j] = '(';
}
// the rest are closing parentheses
for (var j = i + 1 + k; j < n * 2; j++)
{
arr[j] = ')';
}
return true;
}
// if we reached this point it means we got to a maximum
return false;
}Now doing GenerateIncrement(1000000).Take(10) took more to display the results than to actually compute them.
More solutions
As this is a classic interview question, there are a billion solutions to it at LeetCode. Yet the purpose of interview questions is to find out how one thinks, not what the solution of the problem actually is. I hope this helps.