## 1. Preface

My goal for this article is to help you solve technical interview problems similar to the following:

- Generate all subsets of a given set
- Generate all strings over a given alphabet of a given fixed length
- Generate all strings over a given alphabet (of any length)
- Generate all permutations of a given set
- Generate all combinations of a given length and a given set
- Generate all balanced parentheses of a given length
- Generate all binary trees with a given number of nodes

These problems fall under the category of "combinatorial generation" problems, since you are asked to generate all the elements of a set of combinatorial objects (subsets, strings, combinations, permutations, trees, graphs, etc.).

The topic of combinatorial generation is a rich field of study and here I do not intend to do it any real justice. For rigorous and much more comprehensive treatments of the subject I recommend Knuth's or Ruskey's books on the subject. See the Further Reading section for references. Instead, I intend to provide a bare minimum, approachable, and practical guide that will prepare you to approach combinatorial generation problems you might encounter during coding interviews, and to provide you with the basic tools and vocabulary needed to analyze the time and space complexity of your solutions.

I chose to write this post for several reasons. First, I noticed combinatorial generation problems are commonly asked during coding interviews. I myself have been asked variations of combinatorial generation problems on at least six or seven coding interviews that I remember. I suspect their popularity as interview questions has to do with the fact that most of the problems have fairly simple and elegant solutions that are well within reach during a 45-minute coding interview. However, reaching any elegant solution requires clarity of thought, good pattern recognition, a solid understanding of recursion, as well as solid coding skills, in particular comfortable handling of indexes, and general list or string manipulation. There are often many ways of solving a problem, with different levels of space and time complexity trade-off. All of this leads to a problem area that is well-suited for gauging a candidates overall algorithmic thinking and coding aptitude.

Second, the topic is often not given proper treatment as part of most computer science programs. Because of this, I noticed most candidates are somewhat ill-prepared to solve problems in this space. While some students might have encountered a few examples in the space as part of recursion or backtracking topics, the problems are almost never given focused attention by themselves. This article is meant to fill that gap.

Third, I believe the subject matter to be a fantastic playground for exploring ideas and learning more about coding, combinatorics, algorithms, recursion, and time and space complexity analysis, for reasons very similar to those making the subject area a good fit for coding interview questions. As such, combinatorial generation problems provide an excellent excuse to practice and hone coding and algorithmic skills. This article is intended to be an invitation to this playground, providing an approachable and gentle introduction using very readable code in Python.

To make the post useful and practical, I start by providing a brief description of two approaches to solving combinatorial generation problems, and then dive into multiple examples, applying both approaches to each example and then briefly discussing the time and space complexity of each solution. I also provide many exercises as we progress to give you an opportunity to challenge yourself and test your understanding of the material.

## 2. Table Of Contents

A Gentle Introduction To Combinatorial Generation In Python

- 1. Preface
- 2. Table Of Contents
- 3. Preliminaries
- 4. Fixed Length Strings Given An Alphabet
- 5. Permutations Of A Set
- 5.1. Problem Definition
- 5.2. Basic Recursive Solution
- 5.3. Analysis Of Basic Recursive Solution
- 5.4. Exercises
- 5.5. A Better Recursive Solution
- 5.6. Analysis Of The Better Recursive Solution
- 5.7. Exercises
- 5.8. Iterative Solution With Lexicographic Order
- 5.9. Analysis Of The Iterative Solution
- 5.10. Exercises

- 6. Subsets Of A Set
- 7. Combinations Of A Fixed Size
- 8. Balanced Parentheses
- 9. Further Reading

## 3. Preliminaries

### 3.1. Two Approaches To Combinatorial Generation

In this post we will look at two approaches to solving combinatorial generation problems. Let's consider both of them here briefly.

**Recursive**: The problems you are likely to encounter during coding
interviews are very likely to have very simple recursive solutions. The
recursive solution is often based on simple observations about the recursive
structure of the combinatorial set you are generating. At times, the recursive
solution can be as simple as literally following the definition of the
combinatorial set. Combinatorial objects are often defined recursively, for
example, consider the definition of a binary tree. The recursive solutions
often suffer from exponential space usage (or exponential time, or both,
depending on implementation). However, they are often very very simple to
implement, requiring minimal code and are also readable and easy to understand.
As such, you should make sure you master the basic recursive solutions and
provide them as the first solution. This way you will have at least one
working solution by the end of the interview (which will, in my experience of
interviewing candidates, set you apart from the majority of candidates).
Ideally, you should aim to provide a simple recursive solution in 5 to 10
minutes at most, leaving the majority of the rest of the interview time to
space and time complexity analysis and to provide the improved iterative
solution.

**Iterative**: In the iterative approach, we move from one object to the next
by modifying the object in-place. A common iterative approach is to generate
all objects in lexicographic order. This approach has several benefits. First,
since the generation is done by modifying the input in-place, space complexity
is often constant or at least not exponential. Second, it produces the objects
in lexicographic order, meaning the output objects are guaranteed to be in
sorted order. Furthermore, by formulating the problem as how to move from one
object to the next in lexicographic order, we can come up with a general
problem solving strategy that works for many problems. To quote Knuth,
"lexicographic order usually suggests the most convenient way to generate
combinatorial configurations" (The Art Of Computer Programming, Volume 4,
section 7.2.1.3).

We will approach multiple example problems using both the above approaches and analyze their time and space complexity. Hopefully by the end of the article, both approaches will be second nature to you and provide systematic way of approaching any combinatorial generation problem you might encounter.

### 3.2. Time And Space Complexity Of Generation Algorithms

Time and space complexity analysis is slightly different for combinatorial
generation problems. In most cases, the output is exponential in size (or
infinite at times), and hence as a whole the program must run in exponential
time to generate all the objects (or run indefinitely until terminated
externally, in cases of generating infinite sets). Because of this, we will
often consider time needed to generate *each* object in the set (on average, or
worst case). Similarly, we will look at the maximum space needed by the program
at any point during its execution. For programs that need to run indefinitely
(i.e., ones that generate infinite sets), we look at how space usage grows as
the program keeps on running.

Similar to the two approaches to solving the problems, this more nuanced approach to time and space complexity will also be made more clear by looking at multiple examples.

### 3.3. What "Generate" Means

It is important at this point to clarify what we mean by "generate". The simplest way to generate the objects is to simply put all the output into a list or in-memory collection of some sort and returned that collection. However, we obviously can not improve space complexity to be better than the size of the output set (which is often exponential), if we want to keep all the generated objects in memory at once. Therefore, for the purposes of problems like this, "generate" can mean any of the following:

- Place the resulting objects all in a list and return the list.
- Print a representation of each object to standard output.
- Yield each object using a generator.
- Visit each object by calling a provided
`visit`function with the object passed as the argument.

In this article, when we try to avoid unnecessary (and often exponential) memory usage, we will use a simple generator pattern and yield each resulting object instead of placing them in an in-memory collection. You read about Python's generators in PEP 255. As the name of the pattern suggests, Python generators are very well-suited for combinatorial generation.

### 3.4. Output Order

A good clarifying question to ask for combinatorial generation problems is whether there is an expectation on the order of the output objects. You might learn that the output order does not matter, or the interviewer might ask the output to be in lexicographic (i.e., dictionary) order. Rarely, you might also come across a problem that asks for an order that minimizes the difference between two subsequent objects. This order is often referred to as Gray order, named after Bell Labs researcher Frank Gray. I hope to write a follow-up to this post at some point to go over some examples of Gray order generation. For now, in our basic recursive solutions we tend to not worry about the order of the output, and just ensure every object is generated exactly once. For our second approach, we, by definition of the approach, only generate objects in lexicographic order.

## 4. Fixed Length Strings Given An Alphabet

### 4.1. Problem Definition

Let's start by looking at a simple problem: given an alphabet `A` which is
guaranteed to be a non-empty list of distinct single character strings, and a
non-negative integer `n`, generate all strings of length `n`. For
example, given `A = ['0', '1', '2']` and `n = 2` we expect the output to be:

```
00
01
02
10
11
12
20
21
22
```

To make sure the question is clear, let's look at another example. Given `A =
['a', 'b']` and `n = 3` we expect the output to be:

```
aaa
aab
aba
abb
baa
bab
bba
bbb
```

### 4.2. Basic Recursive Solution

The basic recursive structure of the set we are generating can be easily seen as follows: given all strings of length $n - 1$ , we can form all strings of length $n$ by appending all possible characters in the alphabet set to the strings. This leads to the following very basic recursive solution:

```
def strings(A, n):
if n == 0:
return ['']
return [s + c for s in strings(A, n - 1) for c in A]
```

Example usage:

```
In [1]: strings(['0', '1', '2'], 2)
Out[1]: ['00', '01', '02', '10', '11', '12', '20', '21', '22']
```

### 4.3. Analysis Of Basic Recursive Solution

Space usage of this solution is easy to analyze. Let's let $k = len(A)$ , that is $k$ is the size of the alphabet set. We hold the entire output for $n$ in memory, in addition to the output for $n - 1$ . Note that subsequent outputs for strings of length smaller than $n - 1$ can be deallocated as they are no longer needed and we do not keep a reference to them. The total space used by the program can be summarized as $O(k^n + k^{n-1}) = O(k^n)$ . That means we use exponential memory assuming $k > 1$ .

Now let's look at time complexity. The key operation here is appending to a string. It is easy to modify the code to use preallocated lists/strings instead of appending to a string which in Python requires linear work. Let's assume for now that appending to a strong is an $O(1)$ operation. How many string concatenations do we do total? Let's define the total number of concatenations for generating strings of length $n$ as as $T(n)$ . Then we have

$T(n) = k \cdot k^{n-1} + T(n-1) = k^n + T(n-1).$Let's let the base case $T(0) = 1$ for simplicity of the math that follows (as we will see, the exact value of the base does not make a difference in the asymptotic behaviour of the function anyway). The recurrence relation for $T(n)$ is easily solved as

$T(n) = \sum_{i=0}^{n} k^i = \frac{k^{n + 1} - 1}{k - 1} = O(k^n).$Therefore, the total number of concatenations is exponential. However, as discussed
we are more interested in the amount of work done *per string* so we we care
more about

Therefore, we do constant work on average per string generated. A combinatorial generation algorithm that does $O(1)$ work per output object is referred to as a constant amortized time (CAT) algorithm. CAT algorithms are usually considered good solutions (assuming they do not use exponential space, which our solution does!), since they do constant amount of work on average. The only classification better than simply CAT for a combinatorial generation algorithm is for it to be "loopless". Loopless algorithms, as the name suggests, involve no looping per output object, which means they do constant work not just on average but worst case as well. We will not discuss loopless algorithms in this article though as that is a more advanced subject (see resources in Further Reading if you are interested in learning more about loopless algorithms.)

### 4.4. Exercises

*Exercise 4.4.1 (Easy):* What if $k = 1$
? What is the output of the
program? What about space and time complexity?

*Exercise 4.4.2 (Medium):* Modify the recursive solution to modify
preallocated lists of the correct size instead of appending to strings.

*Exercise 4.4.3 (Easy):* Modify the solution to keep count of how many string
concatenations take place. Verify that our closed formula for $T(n)$
is
correct.

*Exercise 4.4.4 (Easy):* Modify the recursive solution to return a generator
instead (i.e., use `yield` instead of `return` and yield one string at a
time instead of returning the whole list).

*Exercise 4.4.5 (Medium):* Analyze the time and space complexity of the
generator solution you came up with in Exercise 4.4.4. How does it compare with
the basic recursive solution?

### 4.5. Iterative Solution With Lexicographic Order

As discussed, the simple recursive solution provided uses exponential memory and because of that, it is not ideal. To provide a better solution, instead of looking at the recursive structure of the set we are generating, we look at the pattern of how we move from one string to the next when we list all the objects in lexicographic order.

First let's look at part of the output for `A = ['0', '1', '2']` and `n =
5`.

```
...
21211
21212
21220
21221
21222
22000
22001
22002
22010
22011
22012
22020
22021
...
```

Let's look at `21222` in this example. The next string is `22000`. How do
we go from `21222` to `22000`? To get to the next item in lexicographic
order we need to increment the first letter that we can, going from right to
left. Going from right to left, the first letter is `2` which is the last
letter in our alphabet (remember our alphabet is `A = ['0', '1', '2'], so
``2` is the last letter). We keep moving left until we find the first letter
that's not a `2`, which is the `1`, the second letter in `21222`. We
change this letter to be the next one in our alphabet, and then we replace
everything following it by the smallest possible lexicographic string which is
`000`, getting `22000`, the result. In fact, if we are clever, we can
replace everything to the right of the `1` with a `0` (here `0` is
special only because it is the first letter in the given alphabet) as we keep
looking for the first letter to increment.

The above leads to the following solution:

```
def strings_2(A, n):
index_of = {x: i for i, x in enumerate(A)}
s = [A[0]] * n
while True:
yield ''.join(s)
for i in range(1, n + 1):
if s[-i] == A[-1]: # Last letter of alphabet, can not increment
s[-i] = A[0]
else:
s[-i] = A[index_of[s[-i]] + 1] # Modify to next letter
break
else:
break
```

Here we use Python's `for` and `else` combination to determine if the
`break` never happened. Notice that `break` does not happen if we never
find any letter to increment, which would imply we are at the very last
lexicographic string.

### 4.6. Analysis Of The Iterative Solution

As before, let $k = len(A)$
, that is $k$
is the size of the
alphabet set. Space usage is again quite simple. We use an additional
dictionary `index_of` which holds $k$
elements in it, and the list
`s` which is of length $n$
. This means our space usage is $O(n) +
O(k) = O(n)$
since we assume $k$
is going to be small, and constant for
most applications. Linear space usage! Not bad at all. In fact, since by
definition of the problem we have to have the generated string in memory this
is the best possible space complexity we are going to get.

Now let's look at time complexity. It is relatively easy to see that the only operation that is repeated per string is is the resetting of trailing occurrences of the last letter of the alphabet. Everything else happens at most once per string. To understand the amortized run-time of the algorithm, we need to find out how many times this operation takes place. Let's call the operation of resetting a trailing occurrences of the last letter of alphabet a "reset" operation for short.

Let $T(n)$ be the total number of reset operations that takes place while generating all strings of length $n$ . For $(k-1)k^{n-1}$ strings, we do zero resets. Then we have $k^{n-1}$ strings for which we reset the very last letter (in addition to possible other letters). This gives us the following recurrence relation

$T(n) = k^{n-1} + T(n - 1),$with $T(0) = 0$ . This is a simple tail recurrence with closed form

$T(n) = \sum_{i = 1}^{n - 1} k^{n-1} = \frac{k^n}{k-1}.$Therefore the amortized run-time of the algorithm is

$\frac{T(n)}{k^n} = \frac{\frac{k^n}{k-1}}{k^n} = \frac{1}{k-1} = O(1).$Therefore, the algorithm, somewhat surprisingly, is CAT. This is intuitive though, since we notice the strings requiring more repetitive work are exponentially rarer while the work is only linearly more (in the extreme, only one out of $k^n$ strings requires $n$ resets).

This makes this algorithm quite ideal for producing strings in lexicographic order as it uses linear space and constant amortized time.

### 4.7. Exercises

*Exercise 4.7.1 (Easy):* Modify the source code provided to count the number
of resets. Experimentally verify that our closed form formula for $T(n)$
is correct.

*Exercise 4.7.2 (Medium):* Assume the alphabet is fixed as `A = [0, 1]` so
you are generating all binary strings of a given length. Simplify the code
assuming this hard-coded alphabet.

*Exercise 4.7.3 (Medium):* The main operation in this algorithm is very
similar to a particular arithmetic operation. What operation is that? Can you
re-implement the algorithm using arithmetic operations? In particular, for the
binary alphabet given in Exercise 4.7.2, can you implement this algorithm very
efficiently using bitwise operations and basic arithmetic?

*Exercise 4.7.4 (Medium):* Modify the `strings_2` solution to just take as
input the alphabet set `A` and generate all strings over that alphabet. Your
program should first generate all strings of length $0$
, then of length
$1$
, then $2$
, and so on.

## 5. Permutations Of A Set

### 5.1. Problem Definition

Let's turn our attention to permutations next. Given a set `A` which is
guaranteed to be a non-empty list of distinct single character strings, we want
to write a program that generates all permutations of it (i.e., all possible
ways to order items in `A`). For example, given `A = ['1', '2', '3']` we
expect the output to be the following (in any order):

```
123
132
213
231
312
321
```

### 5.2. Basic Recursive Solution

Let $n = len(A)$
. Given all permutations of `A[1:]`, we can generate
all permutations of `A` by inserting `A[0]` in all possible $n$
locations. In the example above, there are two permutations of `A[1:] = ['2',
'3']` which are `23` and `32`. We then take `A[0] = '1'` and insert it
in all three possible positions for each of these permutations to get `123`,
`213`, `231` and so on.

Let's turn this into code:

```
def perms_1(A):
if not A:
return [[]]
perms = []
for pi in perms_1(A[1:]):
for i in range(len(A)):
perms.append(pi[:i] + [A[0]] + pi[i:])
return perms
```

The output of this program for `A = ['1', '2', '3']` is shown below:

```
123
213
231
132
312
321
```

Notice that the output is not in lexicographic order.

### 5.3. Analysis Of Basic Recursive Solution

Space usage, as usual, is easy to analyze. Let's let $n = len(A)$ . We hold the entire output for $n$ in memory, in addition to the output for $n - 1$ . Note that subsequent outputs for permutations of length smaller than $n - 1$ can be deallocated as they are no longer needed and we do not keep a reference to them. The total space used by the program can be summarized as $O(n! + (n-1)!) = O(n!)$ . Our memory usage is worse than exponential!

Now let's look at time complexity. The key operation here is inserting `A[0]`
into each sub-permutation. The way we implemented the algorithm, this operation
takes $O(n)$
time, and we do it $n$
times. This gives the following
recurrence:

with $T(1) = 1$ . The tail recurrence is easy to unwrap, giving

$T(n) = \sum_{i=1}^n i\cdot i!.$This sum has a nice and easy closed form given by

$\sum_{i=1}^n i\cdot i! = (n + 1)! - 1.$Therefore, we have $T(n) = (n + 1)! - 1$ . Of course we are interested in the amortized complexity so we look at

$\frac{T(n)}{n!} = \frac{(n+1)! - 1}{n!} = \frac{(n+1)!}{n!} - \frac{1}{n!} = n+1 - \frac{1}{n!} = O(n).$Therefore, the amortized time complexity of our algorithm is $O(n)$ . That means we do, on average, a linear number of operations to generate each permutation. Now, if you are thinking that worse than exponential space usage and linear amortized time do not sound so great, you are right. This is a very naive solution with a pretty bad implementation, but it is a very easy translation of the recursive idea to code. Let's improve it a bit before looking at the lexicographic iterative solution.

### 5.4. Exercises

*Exercise 5.4.1 (Easy):* Write a program that calculates $\sum_{i=1}^n
i\cdot i!$
and $(n + 1)! - 1$
for $1 \le n \le 10$
. Verify that
equality holds for at least the first ten values of $n$
.

*Exercise 5.4.2 (Easy):* Prove $\sum_{i=1}^n i\cdot i! = (n + 1)! - 1$
.
(Hint: try induction.)

*Exercise 5.4.3 (Easy):* Modify the basic recursive function given above to
be a generator instead (i.e., use `yield` instead of `return` and yield one
string at a time instead of returning the whole list).

*Exercise 5.4.4 (Medium):* Analyze the space complexity of the generator
solution you came up with in Exercise 5.4.3. How does it compare with the basic
recursive solution?

*Exercise 5.4.5 (Medium):* Modify `strings_2` to only take `A` as a
parameter, and generate the infinite set of all strings over `A` (also called
the Kleene closure of `A` and written as $A^*$
). Below is the first few
lines of the expected output of the program for `A = ['0', '1', '2']`.

```
''
'0'
'1'
'2'
'00'
'01'
'02'
'10'
'11'
'12'
'20'
'21'
'22'
'000'
...
```

### 5.5. A Better Recursive Solution

A quick improvement to make to the previous solution is to not do linear work
to insert `A[0]` but to instead do everything in-place. Instead, we can move
through each permutation of `A[1:]` recursively, and then move `A[0]` to
the right one at a time. We need to be careful to backtrack at the end because
otherwise the next recursive call will not operate on the right elements of
`A`. Since we do everything in-memory this time, we will use `yield` and
the generator pattern for the recursion.

```
def perms_2(A, starting_index):
if starting_index == len(A) - 1:
yield A
return
for _ in perms_2(A, starting_index + 1):
yield A
# Keep moving A[starting_index] to the right one at a time
for i in range(starting_index, len(A) - 1):
A[i], A[i + 1] = A[i + 1], A[i]
yield A
# Now move it all the way back to where it was at the beginning
for i in range(len(A) - 1, starting_index, -1):
A[i], A[i - 1] = A[i - 1], A[i]
```

Here's how this generator can be used:

```
In [1]: for pi in perms_2(['1', '2', '3'], 0):
...: print(''.join(pi))
...:
123
213
231
132
312
321
```

### 5.6. Analysis Of The Better Recursive Solution

Let's look at space complexity first. It's easy to see that each instance of
the generator uses only constant amount of space (not counting `A` itself
which is given as input). Then the question is how many instances of the
generator are allocated and it is relatively easy to see that one instance,
namely `perms_2(A, i)` is allocated for $0 \le i < n$
, meaning a
total of $n$
total generators are allocated total. This means we use
$O(n)$
space. Not bad!

Now we turn to time complexity. This time, for each permutation of `A[1:]`,
we do $n - 1$
transpositions (repeatedly moving `A[0]` to the right by
swapping it with the element to its right), followed by moving it all the way
back which does another $n-1$
transpositions. This gives the following
recurrence

with $T(1) = 1$ . As before, this is a tail recurrence so we can easily unwrap it as a sum:

$\begin{aligned} T(n) &= \sum_{i=1}^n 2(i-1)(i-1)! \\ &= 2 \cdot \sum_{i=1}^n (i-1)(i-1)! \\ &= 2 \cdot \sum_{i=0}^{n-1} i \cdot i! \\ &= 2n! - 2. \end{aligned}$The amortized time will be

$\frac{T(n)}{n!} = \frac{2n! - 2}{n!} = 2 - \frac{2}{n!} = O(1).$Therefore this improvement was enough to improve the algorithm from linear amortized time to constant amortized time. Simultaneously, by using a generator and doing the transpositions in-place, we improved the space usage of the algorithm from worse than exponential to linear. Overall, this is a pretty solid solution!

### 5.7. Exercises

*Exercise 5.7.1 (Difficult):* You might have noticed the redundancy of moving
`A[0]` all the way to right, only to move it all the way back at the end.
Given that the goal is to have it in all possible positions, we could instead
leave it at the end once it reaches there, permute `A[0:-1]` to the next
permutation, and then move `A[-1]` all the way left, with each transposition
to the left now also being useful (as in each yielding a new permutation).
Modify `perms_2` to do this instead. The output of your program should be
the following for `A = ['1', '2', '3']`:

```
123
213
231
321
312
132
```

*Exercise 5.7.2 (Medium):* Analyze the time and space complexity of your
solution to Exercise 5.7.1.

*Exercise 5.7.3 (Easy):* Consider the output of of the algorithm described in
Exercise 14. How is each permutation different from the subsequent one? How
about the last and the first permutations? What if $n = len(A)$
is even?

### 5.8. Iterative Solution With Lexicographic Order

Now let's try the other approach of finding the next object in lexicographic
order. Very similar to our iterative solution for generating strings, we start
from the right and move left, looking for the first opportunity to modify the
permutation to the next one in lexicographic order. To do this, since we are
dealing with permutations, we will need to find the first element we can move
to the right. We note that this is impossible to do for as long as we have a
decreasing suffix. Therefore, the first step to finding the next permutation in
lexicographic order is to look for the *shortest non-decreasing* suffix.

For example, consider the permutation `7465321`. Going from right to left,
the suffix `65321` is decreasing, and hence it is not possible to modify it
to one that is greater in the lexicographic ordering. However, the suffix
`465321` is no longer decreasing. To get the next permutation in
lexicographic order, we need to move `4` to the right. It is important that
we do this carefully to get the immediate next lexicographic permutation (that
is, we should make sure we do not skip over any permutations). The right
element to swap `4` with is the smallest element in the suffix that is
greater than `4`, which is `5` in this case. We swap `4` and `5` to get
`564321`. Finally, following the established pattern of this approach, we now
need to "reset" everything following the `5` to be the smallest possible in
lexicographic order. This means simply reversing the suffix since we know it is
in decreasing order, and reversing it will sort it. This gives `512346` as
the suffix, giving `7512346` as the final permutation to yield.

Transforming the above algorithm to code gives the following.

```
def perms_3(A):
while True:
yield A
i = len(A) - 1
while i > 0:
if A[i - 1] < A[i]:
break
i -= 1
if i > 0:
# A[i - 1:] is the shortest non-decreasing suffix
j = len(A) - 1
while j >= i:
if A[j] > A[i - 1]:
break
j -= 1
# A[j] is the smallest element in A[i:] that is greater
# than A[i - 1]
A[i - 1], A[j] = A[j], A[i - 1]
A[i:] = A[-1:i - 1:-1]
else:
break
```

### 5.9. Analysis Of The Iterative Solution

Space complexity of this iterative solution is very easy to analyze: we only
use two integer variables `i` and `j` in addition to the input given.
Therefore memory usage of the algorithm is $O(1)$
.

Time complexity is a bit more difficult to analyze but let's give it a shot. It is easy to see that we do at most a linear amount of work for each permutation and hence the algorithm is definitely no worse than $O(n)$ in amortized time. But is it better? It is clear that the number of operations per permutation is a linear function of the length of the shortest non-decreasing suffix. Let's build on this idea.

Given a permutation $\pi$
, let $t(\pi)$
be the length of the
shortest non-decreasing suffix of $\pi$
, and let $t(\pi) = n$
if
$\pi$
does not have any non-decreasing suffixes. (Note that the latter
case only happens for only one permutation, namely the one last in
lexicographic order which is in fully decreasing order). Note that
$t(\pi)$
is exactly `len(A) - i` after the first while loop in our
program. For example, $t(\mathtt{7465321}) = 6$
because
$\mathtt{465321}$
is the shortest non-decreasing suffix of the
permutation.

It is then easy to see that we do $C \cdot t(\pi)$ to get the next permutation given $\pi$ , for some constant $C$ . Therefore, to find the amortized time complexity of the algorithm, we need to find the average value of $t(\pi)$ over all permutations. In other words, we are looking for

$\frac{\sum_{\pi \in \Pi_A}t(\pi)}{n!}$where $\Pi_A$ is the set of all permutations of the set $A$ . Noting that $2 \le t(\pi) \le n$ , let's consider how frequently various values for $t(\pi)$ occur.

First let's look at $t(\pi) = 2$ . This means $\pi[-2] > \pi[-1]$ (using negative indexing in math notation with the exact same semantics as in Python). How many permutations have this property? Exactly half, because there is a one-to-one correspondence between permutations that have this property, and ones that do not (namely, swapping the last two elements is the bijection). Therefore, for $\frac{n!}{2}$ of the permutations we have $t(\pi) = 2$ .

How about $t(\pi) = 3$ ? This means $\pi[-3] > \pi[-2]$ while $\pi[-2] < \pi[-1]$ . How many permutations have this property? Noting that this property places an exact ordering requirement on the last three elements of the permutation, it is easy to see that given the total $3! = 6$ total possible sub-permutations of the last three elements of a given permutation, only one of them satisfies this property. Therefore, $\frac{n!}{3!}$ of all permutations have $t(\pi)=3$ .

Generalizing the same argument, we get

$\begin{aligned} \sum_{\pi \in \Pi_A}t(\pi) &= \sum_{i=2}^n i \cdot \frac{n!}{i!} \\ &= \sum_{i=2}^n \frac{n!}{(i - 1)!} \\ &= n! \sum_{i=1}^{n-1} \frac{1}{i!}. \end{aligned}$The last summation in the previous equation might look familiar if you have some calculus background. Let's recall one of possible definitions of the mathematical constant $e$ :

$\sum_{i=0}^{\infty} \frac{1}{i!} = e.$Using this identity, we have

$\sum_{i=1}^{n-1} \frac{1}{i!} < e - 1.$Therefore, we have

$\sum_{\pi \in \Pi_A}t(\pi) = n! \sum_{i=1}^{n-1} \frac{1}{i!} < n! (e - 1).$Substituting this back into the original equation for amortized time complexity we get

$\frac{\sum_{\pi \in \Pi_A}t(\pi)}{n!} < \frac{n! (e - 1)}{n!} = e - 1 = O(1).$Therefore, this algorithm is CAT. Combined with $O(1)$ space usage, this means this algorithm is quite efficient.

### 5.10. Exercises

*Exercise 5.10.1 (Easy):* Modify `perms_3` to sum over all values of
`len(A) - i` for all the generated permutations. This is equivalent to
calculating $\sum_{\pi \in \Pi_A}t(\pi)$
. Divide the result by $n!$
and verify that for $1 \le n \le 10$
the result of the division is
approaching $e -1 = 1.71828\ldots$
.

*Exercise 5.10.2 (Medium):* In `perms_3`, we do one pass to find the right
element to swap `A[i - 1]` with (i.e., the while loop that finds the right
value for `j`), and then effectively another loop to reverse `A[i:]`.
Combine these two loops into the same loop by reversing `A[i:]` as you look
for `j`.

## 6. Subsets Of A Set

### 6.1. Problem Definition

Given a set `A` which is guaranteed to be a non-empty list of distinct single
character strings, generate all of its subsets. For example, given `A =
['1', '2', '3']` we expect the output to be the following (in any order):

```
''
'1'
'2'
'3'
'12'
'13'
'23'
'123'
```

Alternatively, we can represent the subsets using binary strings of length $n$ where bit $i$ being set indicates $A[i]$ is in the subset. The output using this representation corresponding to the above output is given below:

```
000
100
010
001
110
101
011
111
```

You might have noticed that using the latter representation of binary strings, the problem is reduced to one we have already solved. In fact, the most efficient solution to the problem of generating all subsets is more or less the same as the answer to Exercise 4.7.3. We will look at this when we consider the lexicographic solution to this problem.

### 6.2. Basic Recursive Solution

Given the set `A`, we can generate all subsets by first generating all
subsets of `A[1:]`, all of which are also subsets of `A`, and then adding
`A[0]` to them to get all the subsets. This leads to the following very basic
recursive solution:

```
def subsets(A):
if not A:
yield []
else:
for s in subsets(A[1:]):
yield s
yield [A[0]] + s
```

### 6.3. Analysis Of Basic Recursive Solution

As is convention by this point, let's look at space complexity first. Each
instance of the generator needs memory to store the argument it is called with,
and creates new lists to generate one at a time. Therefore, `subsets(A)` called
with $A$
of size $n$
will use memory $C_1\cdot n + C_2$
for some
constants $C_1$
and $C_2$
. With the recursive call stack reaching the end at
$n=0$
, we have the total memory usage as

For time complexity, we observe that a recursive call for a set of size $n-1$ is made so we do $T(n - 1)$ work minimum, and then for each subset $s$ of $A[1:]$ we create a new list of size one greater than the size of the subset $s$ . The run-time cost of creating such a set is linearly proportional to the size of the list as a copy of the list is made. Therefore, all in all, the appending of $A[0]$ will require $2^{n-1}$ operations, and the copying over of $s$ , the sum of the number of all elements in $s$ . The sum over all the lengths of $s$ is not immediately obvious. Let's dig into it a bit.

The question can be rephrased as the following: if you write all the subsets of a set $A$ , and then sum over the lengths of all these subsets, what do you get? Let's look at an example with $n=3$ :

```
'' 0
'1' 1
'2' 1
'3' 1
'12' 2
'13' 2
'23' 2
'123' 3
Sum 12
```

This is a fun little mathematical puzzle that I encourage you to think about before reading further. One easy way to arrive at the answer is to think about how many times a single element is included in the sum, which is $2^{n-1}$ since exactly half the subsets contain it and half don't. Therefore, the number we are looking for is $n 2^{n-1}$ . Putting this all together we get

$\begin{aligned} T(n) &= T(n-1) + (n - 1) 2^{n-2} + 2^{n - 1} \\ &= T(n-1) + (n - 1) 2^{n-2} + 2 \cdot 2^{n - 2} \\ &= T(n-1) + (n + 1) 2^{n-2} \\ &= \sum_{i=1}^n (i+1) 2^{i-2} \\ &= \frac{1}{2^3} \sum_{i=1}^n (i+1) 2^{i+1} \\ &= \frac{1}{2^3} \sum_{i=2}^{n+1} i 2^i \end{aligned}$Here we can use the following identity to simplify the sum:

$\sum_{i=1}^{n} i \cdot c^{i} = \frac{n c^{n+2} - (n+1) c^{n+1} + c}{(c-1)^2}.$Applying this to $T(n)$ gives

$\begin{aligned} T(n) &= \frac{1}{2^3} \sum_{i=2}^{n+1} i 2^i \\ &= \frac{1}{2^3} (\sum_{i=1}^{n+1} i 2^i - 2) \\ &= \frac{1}{2^3} ((n+1)2^{n+3} - (n+2) 2^{n+2} + 2 - 2) \\ &= \frac{1}{2^3} (2(n+1)2^{n+2} - (n+2) 2^{n+2}) \\ &= \frac{1}{2^3} ((2n+2 - n - 2)2^{n+2}) \\ &= \frac{1}{2^3} n 2^{n+2} \\ &= n 2^{n-1}. \end{aligned}$Therefore, the total number of copy operations performed to generate all subsets is $n 2^{n-1}$ . The amortized run-time then is given by

$\frac{T(n)}{2^n} = \frac{n 2^{n-1}}{2^n} = \frac{n}{2} = O(n).$This means we have Linear amortized run-time, which means this is not a very good solution.

### 6.4. Exercises

*Exercise 6.3.1 (Easy):* Modify the code to sum over the lengths of the new
lists created in the loop (i.e., sum over `len([A[0]] + s)`) over all the
subsets generated. Verify that our formula of $T(n) = n 2^{n-1}$
correctly calculates this number.

*Exercise 6.3.2 (Medium):* Prove the identity we used to simplify the sum.
Namely, prove

Hint: use induction.

*Exercise 6.3.3 (Easy):* We were a little sloppy with how we handled the
recurrence relation for $T(n)$
. Specifically, we did not specify the base
case. What is the correct base case? Does it affect the calculations and how
the recurrence was expanded to a sum?

### 6.5. Iterative Solution With Lexicographic Order

For the iterative lexicographic order approach, let's consider an alternative representation of subsets. Given $A$ of size $n$ , we can represent a subset of $A$ as a binary string of length $n$ in which each element in $A$ is present in the subset if and only if the corresponding bit in the binary string is set to one.

The table below shows all subsets of `A = ['1', '2', '3']` in both
representations.

```
Subset Corresponding binary string
'' 000
'1' 001
'2' 010
'12' 011
'1' 100
'13' 101
'12' 110
'123' 111
```

Representing subsets in this format, the problem is reduced to one we have already solved. Namely, we need to generate all binary strings. Since we already solved this problem in generalized case, here I provide a quick and optimized version that generates all binary strings of length $n$ in lexicographic order using arithmetic and then show how we can use simple bitwise operations to extract the subset given the binary string.

```
def subsets_2(A):
n = len(A)
for k in range(1 << n):
yield [A[i] for i in range(n) if k & (1 << i)]
```

I leave the time ans space complexity analysis of this solution as exercises below.

### 6.6. Exercises

*Exercise 6.6.1 (Easy):* Analyze the space complexity and the amortized
run-time complexity of the `subsets_2` solution above.

## 7. Combinations Of A Fixed Size

### 7.1. Problem Definition

Having looked at generating all subsets, next natural step is to turn our
attention to the problem generating subsets of a certain size, also known as
combinations of a set—after all, we are looking at *combinatorial* generation
problems! Given a set $A$
of size $n$
, and an integer $0 \le
k \le n$
, we want to generate all subsets of $A$
of size $k$
. For
example, given `A = ['1', '2', '3', '4']` and $k=2$
we should generate
the following:

```
12
13
14
23
24
34
```

As you might remember from basic discrete mathematics,

$\binom{n}{k} = {4 \choose 2} = \frac{4!}{2! \cdot 2!} = \frac{24}{4} = 6$subsets are listed.

In general, the size of the output, which is the number of combinations of size $k$ chosen from a set of size $n$ , is given by ${n \choose k}$ , which is read "$n$ choose $k$ . We have

${n \choose k} = \frac{n!}{(n-k)!k!},$which is fairly easy to prove using a basic counting argument.

There is another way to represent combinations in a program. Similar to how subsets of a set of size $n$ can be represented as binary strings of length $n$ , we can represent combinations of size $k$ chosen out of a set of size $n$ as binary strings of length $n$ in which exactly $k$ bits are set to one. Using this representation, the above list of combinations becomes the following:

```
1100
1010
1001
0110
0101
0011
```

We will look at generating the combinations using both of these representations.

### 7.2. Basic Recursive Solution

Suppose you are given $n$ items and asked to choose $k$ out of them. To do this, you pick the first item and look at it. You have two options. You either pick the item, in which case you have reduced the problem to that of choosing $k-1$ items from the $n-1$ items left, or you can choose not to pick the first item in which the problem is reduced to choosing $k$ from the $n-1$ items left. This observation leads to the recurrence ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$ . Of course, the right base cases need to be stated here (see the exercises section coming up).

Following the exact same logic, we can write a very basic recursive solution:

```
def combinations(A, k):
if k == 0:
return [[]]
if len(A) == k:
return [list(A)]
result = [[A[0]] + c for c in combinations(A[1:], k - 1)]
result += combinations(A[1:], k)
return result
```

### 7.3. Analysis Of Basic Recursive Solution

For space complexity, we keep the entirety of ${n choose k}$ combinations in memory each of which is a list of length $k$ . Therefore, we are looking at the following space complexity:

$k\dbinom{n}{k} = k \frac{n!}{k!(n-k)!} = \frac{n!}{(k-1)!(n-k)!}.$Assuming $k$ is constant and small relative to $n$ , we can fairly easily see that the above is $O(n^k)$ . However note that if $k$ is not constant, and is closer to $\frac{n}{2}$ ,

Note that in practice we store both $(k-1){n - 1 \choose k - 1}$ and $(k-1){n \choose k - 1}$ space concurrently with the larger $k{n \choose k}$ space allocated for the larger list due to the recursive calls but since it is easy to see both of those lists use less space than the larger list, storing them concurrently only increases memory usage by a constant factor of the memory used to store the end result. Therefore the big-O characterization of the space complexity of the algorithm above is still correct even though we did not take the extra lists created by the recursive calls into account.

Amortized run-time complexity analysis of this solution is a bit tricky. I am leaving it as an exercise for those of you interested in a challenge.

### 7.4. Exercises

*Exercise 7.4.1 (Easy):* State the correct base case conditions for the
recurrence ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$
.

*Exercise 7.4.2 (Easy):* Prove that assuming $k$
is constant we have
$\frac{n!}{(k-1)!(n-k)!} = O(n^k)$
.

*Exercise 7.4.3 (Difficult):* Analyze the amortized run-time complexity of the
`combinations` function as a function of $n$
and $k$
.

### 7.5. Iterative Solution With Lexicographic Order

For an iterative solution, let's consider the alternative binary string representation as it lends itself to a simpler lexicographic order iterative solution. Since in this representation the set we are choosing from itself does not matter, we modify our code to simply accept the size of the set, $n$ , instead. Here is what the output should be for $n=4$ and $k=2$ :

```
0011
0101
0110
1001
1010
1100
```

As before, the strategy is to find the first element we can increment going
from right to left. In this case, to increment an element we need to change it
from `0` to `1`. To do that, we need to change another `1` to a `0`.
Noticing all this it is fairly easy to reason that what we should look for is
the first instance of `01` which we will then replace with `10`. Afterwards
we have to reset everything following the `10` to be the smallest
lexicographic element that has the right number of ones and zeros. To do this,
we need to keep track of how many ones we encounter. Finally, we note that the
last item in lexicographic order will always be `11...1100...00` which does
not have a `01` in it, and hence if we can't find such an occurrence we know
we are at the end of the generation. Here is the implementation of this
algorithm:

```
def combinations_2(n, k):
c = [0] * (n - k) + [1] * k
while True:
yield c
# Look for the right-most 01 while counting ones encountered.
i = n - 2
ones = 0
while i >= 0 and c[i:i + 2] != [0, 1]:
if c[i + 1] == 1:
ones += 1
i -= 1
if i < 0:
break
# Change the 01 to 10 and reset the suffix to the smallest
# lexicographic string with the right number of ones and zeros.
c[i:] = [1] + [0] * (n - i - ones - 1) + [1] * ones
```

Space complexity of this solution is rather trivial but amortized run-time complexity is a bit tricky. I am leaving both of them as exercises below as by now you should have enough experience with the analysis to be able to tackle them on your own.

### 7.6. Exercises

*Exercise 7.6.1 (Easy):* Write a function `convert` that given a list A and a
binary string of length $n$
returns returns the corresponding subset of
$A$
. For example, `convert([1, 2, 3, 4], [0, 1, 0 ,1])` should return
`[2, 4]`.

*Exercise 7.6.2 (Easy):* Using the function you wrote in the previous exercise,
modify the `combinations_2` to take a list `A` as the input instead of
$n$
and have it yield subsets of size $k$
of the list `A`.

*Exercise 7.6.3 (Medium):* Prove that the first `01` going from right to left
is the first index in which we can switch a `0` and a `1` to get to the
next combination in lexicographic order.

*Exercise 7.6.4 (Easy):* Analyze the space complexity of the `combinations_2`
solution.

*Exercise 7.6.5 (Difficult):* Analyze the amortized time complexity of the
`combinations_2` solution.

## 8. Balanced Parentheses

For the balanced parentheses problem I will simply refer you to my previous in depth article on generating balanced parentheses, where I discuss the problem definition, several equivalent problems, and provide a simple recursive solution as well as several iterative solutions and dive into the time and space complexity analysis of the solutions.

## 9. Further Reading

Donald Knuth's Art of Computer Programming Volume 4 goes into depth on combinatorial generation. Frank Ruskey also has an excellent book on the subject titled Combinatorial Generation.

You might also find my post on combinatorial generation in Python using coroutines interesting after reading this article

## Comments