How to solve permutations and combination coding problems
--
Permutations refer to different ordered selections of elements in a collection of candidates, whereas combinations refer to different unordered selections of elements. They are common coding problems and may seem daunting at first sight. This is because there are many possible selections from potential candidates, how can we be sure that we have considered all?
To systematically find all the selections, we need to incrementally build candidates to the solutions. To do so, drawing out each selection in the form of a ‘decision tree’ can greatly help save our brain.
In this post, I’ll focus on some classic permutation and combination problems from Leetcode. This is the stepping stone to solving more complicated problems using backtracking and dynamic programming.
Problems
Permutations
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Drawing out the decision tree:
We start with an empty list and incrementally append elements from our potential candidates. For the first decision, we can select any element from the input [1, 2, 3]. This can be achieved using a for loop to iterate the list and append the element to our temporary list. This is equivalent to creating three splits in the tree below. To go further along each split, we have one fewer candidate to select. For example, if we selected 1 in the first branch, the potential candidates left are [2, 3] for branches below 1. So we have to remove 1 from the input list.
We typically use recursion to solve this kind of problem because it is easier to keep track of all the partial solutions: just incrementally build the solution as function inputs to the recursive function. The tree will be built following a depth-first-search manner.
Note that to remove an element from the input list, we can’t use the remove() function like below:
nums.remove(nums[i]) This is because remove() will remove the elements from the global input list. We will have nothing left after the first branch. So we have to use indices to select the portion of the input list or use list slicing to remove already selected elements while not affecting the global input list. In my opinion, start with list slicing then optimize to use indices will reduce potential mistakes.
We also need to take care of the ending conditions, e.g. after we reach the leaf nodes, we need to stop. This happens when the potential candidates become empty.
The solution:
- Time complexity: O(n x n!) as there are n! permutations and n for the cost of list slicing.
- Space complexity: O(n x n!) as we have to store all n! permutations and for each permutation, we store a slice of the input.
Take a look at the last line, when i reaches the last index of nums, wouldn’t nums[i+1:] be out of range of nums? Though i+1 will be out of range, list slicing with indices out of range does not result in an error. For example:
>>> nums = [1, 2, 3]
>>> nums[3:]
[]This is just some implementation details about Python list. You may want to check here for more details.
Let’s take a look at a slightly more complex problem.
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:[[1,1,2], [1,2,1], [2,1,1]]
We can sort the input list first so that checking whether an element is a duplicate is just one comparison with the next element (be careful of the last element as a special case). If not, we have to check all the other elements, which takes O(N²) time.
To check whether an element is a duplicate:
for i in range(len(nums)):
if (i+1 < len(nums) and nums[i] != nums[i+1]) or i+1 == len(nums):
# grow the branch from nums[i]All the rest of the solution will be the same as the previous one.
Build the search tree:
See how the solution is similar to the previous one:
The above problems are array problems. Now let’s look at permutations for strings.
17. Letter Combinations of a Phone Number
Given a string containing digits from
2-9inclusive, return all possible letter combinations that the number could represent.A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Build the search tree:
The solution:
- Time complexity: 3^N x 4 ^M where N is the number of digits that map to 3 letters and M is the number of digits that map to 4 letters in the input
- Space complexity: 3^N x 4 ^M to store all solutions.
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()”]
For all the previous problems, there is no constraint in deciding the number of splits. We just iterate through all the potential candidates and create a split for each selected candidate, skipping the duplicates. However, for this problem, we have to consider the relative number of open and close brackets when deciding on the splits.
Draw out the decision tree:
The solution:
Note that the only difference from the previous solutions is the condition checking before making the splits in the decision tree.
- Time complexity: O(2 ^ 2n). Look at the decision tree. For a tree with a branching of a and depth d, the number of nodes in total is 1 + b + b² + b³ + …b^(d-1). This value is the sum of the geometric sequence whcih is ~O(b^d).
- Space complexity: O(2 ^ 2n) as we have to store all the nodes.
So far we have looked at some permutation problems, let’s move on to combination problems.
Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:
Input: n = 4, k = 2
Output: [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
For combination problems, as the order is not important, we don’t need to consider the elements before the current element:
The solution:
The only difference from permutations is that we slice the list to num[i+1:] whereas for permutations, we also include the part before i: nums[:i]+nums[i+1:]
- Time complexity: O( k x (n choose k)). We have (n choose k) number of combinations, and list concatenation costs k where k is the number of elements in each combination.
- Space complexity: O(n choose k)
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output: [[3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []]
Draw out the decision tree:
The solution:
The only difference from the previous problem is that we append all the tree nodes to our result.
- Time complexity: O(Nx 2^N). If we look at the decision tree, we created ~2^N subsets, and list concatenation for each subset which costs N.
- Space complexity: O(Nx 2^N)
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2]
Output: [[2], [1], [1,2,2], [2,2], [1,2], []]
Draw out the decision tree:
To skip duplicates, we check each element with the previous one, instead of the next one. Try out for yourself to understand the difference.
The solution:
Conclusion
The basic building block to solve permutation and combination problems is to understand the use of recursion in a for loop. Hopefully, you have seen how helpful it is to draw out the decision tree to trace how recursion works to incrementally select candidates from a changing candidate pool.
Acknowledgments
