How to generate all combinations given an array of elements using backtracking?

Question

Given an array, generate all combinations

For example:

Input: {1,2,3}

Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}

I am practicing Backtracking algorithms and I think I understand the general idea of backtracking. You are essentially running a DFS to find the path that satisfies a condition. If you hit a node that fails the condition, exit the current node and start at the previous node.

However, I am having trouble understanding how to implement the traverse part of the implicit tree.

My initial idea is to traverse down the left most path which will give me {1}, {1,2}, {1,2,3}. However, once I backtrack to 1, how do I continue adding the 3 to get {1,3} and {1,3,2} afterwards? Even if I have 2 pointers, I would need it to point to the 2 to eventually get {1,3,2}.

Am I approaching this problem correctly by drawing this implicit tree and trying to code it? Or is there another approach I should take?

I am not looking for code to solve this, rather I am looking for some insight on solving these kinds of questions.

Answer 1

I wrote the description below thinking that you were asking for all combinations of elements. However, at second glance it is unclear. I'll describe both cases.

Combinations

So let's talk about the number of combinations. If you're trying to pick $k$ numbers from $1,2,...,n$, there's $2^n$ ways. $$\sum_{k=0}^n{n\choose k} = 2^n$$

This is a subtle hint that you can think of a combination as a set of binary choices. Let us have $n$ levels in our search tree, not including the root level. At level $i$, we give ourselves the choice to add or not to add element $i$ to our current combination. In this way, we construct a tree of uniform depth such that any path from root to leaf constructs a unique combination and we also claim that all possible combinations are represented by the tree. Now we can just compute a DFS, and every time our search reaches a leaf node, we add the current path to the list of combinations (If you're wondering how to keep track of the current path, there are already many posts/resources about that). If you prefer to do it recursively, this is also trivial.

The difficult part of these problems is indeed coming up with the representation. Let's go back and take a look at your original proposal.

Permutations

Again lets think of our choices at every step. We construct a tree to represent these choices. At a node $p$ at level $i$, we can select any of the remaining numbers not present in the path $root\rightarrow ...\rightarrow p$. Therefore, every root to leaf path in our tree now represents a permutation of all $n$ elements. In order to also get the permutations of subsets of $1,2,...,n$, we consider all paths in the tree beginning at the root as possible permutations.

This seems to be what your tree depicts, and it is a common way to view the problem. Simply performing a DFS while keeping track of the current path should be sufficient to obtain an answer.

Answer 2

I see two ways of doing it / thinking about it, which are essentially equivalent.

Method 1: Use recursion to implement your DFS. When at a node of your tree, you just need to recursively call the DFS on every child node, then output/store the current node (or the other way around). The backtracking will take care of itself. If you don't want to use recursion you can simulate the call stack yourself.

Method 2: Remember from where you came when backtracking. So for example, when backtracking from {1,2} to {1}, keep a variable that says "I deleted 2". That way, you know that you just came back from the branch where 2 was added, so you can go down the path where you add 3. This is essentially what recursion will do for you, except that in this particular case all the information you need is already stored in the last combination you visited, so there is no need for an additional stack or recursion.