I was recently trying to solve a practice interview question that asked for every sub-array of an input array. My terrible solution involved a permutation O(n!) of the input array, an iteration over each permutation O(n), and a sort O(n^2). My computer couldn't handle an input array of more than eight or so elements. I was inspired by this awful function to learn how to finally write a combination function.
Combination functions are one of those functions that you won't use that often. However, when you do need to find all subsets, knowing how to write one will save you a lot of time (and time complexity), code, and frustration. It only takes about ten lines. Combination functions also come up during interviews so it's well worth your time learning this simple algorithm.
Combinations Versus Permutations
A permutation is every possible arrangement of an input. The length of every permutation is equal to the length of the input. An anagram is a great example. Permutations of the 'abc' include 'acb', 'bac', 'bca', 'cab', and 'cba.' Order does matter.
A combination can be constructed from an input. It's a subset of an input. All possible combinations of 'abc' include 'a', 'b', 'c', 'ab', 'ac', 'bc', and 'abc.' Order does not matter in in the eye of a combination: 'ab' and 'ba' are the same thing.
Combination Function Structure
This function will produce all combinations of an array. First, I'll define my function. I'll create a results array which will be returned at the end of the function. I used the keyword let instead of const because I'll reassign later in the function. I'll also set up a for loop to iterate over the array. I don't need the index so a for of loop will make the function a little cleaner.
Next, I'm going to set up my inner loop. I need to create a temporary array to store the results from the inner loop which will be added to the results array. I'm using the ES6 spread operator to set results equal to an array that contains all the elements in the results array and all the results in the temp array.
The hardest thing for me to understand when learning how to write this function was that the temp array must start with the current value of the outer loop. This is the key to making this function work. More on this later.
The last thing to do is push something into the temp array. In this example, I need to push an array that contains all the elements in result and the current element.
The following code snippet, in general, will solve most combination problems. Since this function is generating array combinations, I had to add a few things to make it work. These additions are specific to this problem and will vary from problem to problem.
What's Actually Happening
If I run this function and I pass in ['bears', 'beets', and 'battlestar galactica'], I get seven results. Prior to the first iteration of the inner loop, the state of the function is as follows:
results = []
temp = ['bears']
I iterate over results. There's nothing in results so after the first iteration, temp contains one element, 'bears.' I concatenate that to results (which is currently empty) so results now equals ['bears'].
Prior to the second iteration of the outer loop, the state of the function is as follows:
results = ['bears']
temp = ['beets']
The inner loop has one iteration (only one result in results). I push ['bears', 'beets'] onto temp (which is currently equal to ['beets']) and get [['beets'], ['bears', 'beets']]. I concatenate this with results and get [['bears'], ['beets'], ['bears', 'beets']].
Prior to the third iteration of the outer loop, the state of the function is as follows:
results = [['bears'], ['beets'], ['bears', 'beets']]
temp = ['battlestar galactica']
The last iteration will follow the same process and the end results will be an array that contains seven arrays.
It's a little confusing but if you write it out on paper it makes a lot of sense. It's a fun little algorithm that doesn't take too long to learn and is convenient to have in your back pocket.
Top comments (0)