Combinations and Permutations with an Intro to Backtracking

Combinations and Permutations are a common set of interview problems that require generating various sequences based on rules.

You can solve this problem with an iterative or recursive solution. I will work out the intuition behind both examples and discuss the pros and cons between them.

The standard input output of the question requires us to build out the list of all possible combinations of size 2 given an input.

Input: n = [1,2,3,4]; k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

Recursive Solution

The combination is any 2 pairs from the list [1,2,3,4]. A brute force solution would start from the first number in n, which is 1 and make a pair with every other number, then remove duplicates. There is an optimization where we can produce combinations by limiting our options at every step. First, we take 1and make a pair with every other options. Since our combinations size k is 2, we don’t continue creating combinations.

[1, 2],
[1, 3],
[1, 4],

We then remove 1 from the set of options and proceed to do the same steps with the remaining options:

[2, 3, 4], [3, 4], [4]

Starting with 2 and then 3 we arrive at the rest of the combinations.

[2, 3]
[2, 4]
[3, 4]

By the time we get to 4 there are not enough elements to continue the pattern so we stop.

If we had a depth of 3 for example:

Input: n = [1,2,3]; k = 3
Output:
[
[1, 2, 3],
]

The graph of our choices unfolding as we build out our options is shown below.

Image for post
Image for post

At every point in the creation of the combination we choose the next number from an available set of options. For a recursive solution the first step would be to think of a base case, which would be len(n) == k or k == 0. At this point we have found a combination, and we add it to our list of discovered paths.

If our path is not equal to size k we iterate through all our branching choices and build out the path. The key part for combinations is that once you have used an option, you remove it before you pass it down to the next recursive step.

The permutation case will also be quite similar, the only difference being that we modify the options that we pass down every level to include everything except the current choice.

Image for post
Image for post

The code is similar, and the only change is
combine_helper(ans, path+[num], options[0:index] + options[index+1:], count — 1) . The slicing method options[0:index] + options[index+1:] just takes everything from the beginning of the array up to the current index, and extends the array with everything from beyond the current index to the end of the array.

Choose, Explore, Unchoose

The key intuition the problems above is a type of solutions exploration. In our algorithms we pass along a set of existing choices, then we recursively explore the rest of the options until we arrive at a valid combination or permutation or we terminate and return nothing for that branch.

This class of problems follows a general pattern called Choose, Explore, Unchoose. It is also known as recursive backtracking and more examples can be found in the lecture notes from Stanford.

This class of problems follow a general template.

function backtracking(choosen):   if valid_solution?(choosen):      perform_action_with(choosen) // save, print, etc   else:      for each option we can take here:
choosen = choose_one(option) // choose
backtracking(choosen) // explore
choosen = unchoose(option) // unchoose

You can visualize the tree as it builds with this structure. As you make more choices we branch out and apply different logic to choose the next steps.

It is quite similar to the recursive structure, but the backtracking template allows a more structure that makes it easier to extend to other use cases such as permutations without much change.

Iterative Solution

Now that we seen the backtracking structure we can write an iterative solution to the combination problem. The crux of this solution is that backtracking is a form of depth first search (DFS) algorithm, and DFS has an iterative implementation.

Image for post
Image for post

We keep track of all combinations in a stack, and at every depth we expand it with the new options in that level of the tree. It is generally more complex than the recursive or backtracking solution.

start_index = nums.index(combo[-1]) + 1 if len(combo) > 0 else 0

Here instead of having a nice recursion structure to handle the logic to limit our options every depth, we had to manually retrieve the last position in the combination, locate the index that it is at in our options and then limit the list of options from there. Overall, it is more intuitive to derive a recursive or backtracking solution prior to using an iterative solution.

The rules for providing the available options to the next layer is easier to see with a backtracking solution versus a iterative one.

The permutations solution is a bit simpler, but it varies with variants of the permutation and combinations problems.

Conclusion

Backtracking is a common template that applies to many problems where we have to make successive choices to arrive at a solution. In this 2 problem sample the iterative solutions derives from a good grasp of the backtracking implementation.

Overall, it is more intuitive to derive a recursive or backtracking solution prior to using an iterative solution.

🤓 I like learning boring complicated stuff and making it sound easy. 💻 🤔

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store