Theory

Using Breadth First Search (BFS) approach to handle permutations/combinations problems.

Questions

Given a set with distinct elements, find all of its distinct subsets.

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.

Time complexity

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.

Space complexity

O(n2^n), since we store all these subsets.

Given a set of numbers that might contain duplicates, find all of its distinct 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]}.

Time complexity

O(n2^n)

Space complexity

O(n2^n)

Given a set of distinct numbers, find all of its permutations. Permutation is defined as the re-arranging of the elements of the set.

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]

Time complexity

Number of permutations = n!. To insert an element into each positiin, we traverse n times. Thus, time complexity, is O(n * n!).

Space complexity

O(n * n!)

Return to Index