Using Breadth First Search (BFS) approach to handle permutations/combinations problems.
Example 1:
Input: [1, 3]
Output: [], [1], [3], [1,3]
Example 2:
Input: [1, 5, 3]
Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3]
Implementation: Subsets
We start with an empty set, then iterate through the numbers to create new subsets. E.g.
Input: [1, 3, 5]
{ [] }
add 1:
{ [], [1] }
add 3:
{ [], [1], [3], [1,3] }
add 5:
{ [], [1], [1,5] [3], [3,5], [5], [1,3], [1,3,5]}
Point of observation is when adding a new element, we are copying over the previous set and not amending to it.
At each step, the number of subsets double since we are adding each element to the all existing subsets. So we will have 2^n subsets. Since there are n numbers in the list, we will have O(n2^n) complexity.
O(n2^n), since we store all these subsets.
Example 1:
Input: [1, 3, 3]
Output: [], [1], [3], [1,3], [3,3], [1,3,3]
Example 2:
Input: [1, 5, 3, 3]
Output: [], [1], [5], [3], [1,5], [1,3], [5,3], [1,5,3], [3,3], [1,3,3], [3,3,5], [1,5,3,3]
Implementation: DuplicateSubsets
We can follow the same approach as before, but, to deal with duplicates, do the following:
1. Sort the array so the duplicates are next to each other.
2. When we encounter a duplicate (arr[i-1]=arr[i]), we only create new subsets from the last set of created subsets. Why? Let's take an example:
[1, 3, 3]
We start with []
For 1: { [], [1] }
For 3: { [], [1], [3], [1,3] }
For 3: Since, this is a duplicate, if we consider all subsets, we will get:
{ [], [1], [3], [1,3], [3], [1,3], [3,3], [1,3,3] }, which would give us non-unique {[3],[1,3]}.
However, in the iteration before, we created {[3],[1,3]}; if we just choose those, we get the two unique subsets that we require: {[3,3],[1,3,3]}.
O(n2^n)
O(n2^n)
For example, {1, 2, 3} has the following six permutations:
{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}
If a set has ‘n’ distinct elements it will have n! permutations.
Example 1:
Input: [1,3,5]
Output: [1,3,5], [1,5,3], [3,1,5], [3,5,1], [5,1,3], [5,3,1]
Iterative solution: PermutationsIterative
This problem follows the Subsets pattern and we can follow a similar Breadth First Search (BFS) approach. However, unlike Subsets, every permutation must contain all the numbers.
Let’s take the example-1 mentioned above to generate all the permutations. Following a BFS approach, we will consider one number at a time:
If the given set is empty then we have only an empty permutation set: []
Let’s add the first element (1), the permutations will be: [1]
Let’s add the second element (3), the permutations will be: [3,1], [1,3]
Let’s add the third element (5), the permutations will be: [5,3,1], [3,5,1], [3,1,5], [5,1,3], [1,5,3], [1,3,5]
Let’s analyze the permutations in the 3rd and 4th step. How can we generate permutations in the 4th step from the permutations of the 3rd step?
If we look closely, we will realize that when we add a new number (5), we take each permutation of the previous step and insert the new number in every position to generate the new permutations. For example, inserting ‘5’ in different positions of [3,1] will give us the following permutations:
Inserting ‘5’ before ‘3’: [5,3,1]
Inserting ‘5’ between ‘3’ and ‘1’: [3,5,1]
Inserting ‘5’ after ‘1’: [3,1,5]
Number of permutations = n!. To insert an element into each positiin, we traverse n times. Thus, time complexity, is O(n * n!).
O(n * n!)