Backtracking: Generating Permutations
Summary
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Test cases:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Input: nums = [1]
Output: [[1]]
Input: nums = []
Output: []
Algorithm
Please refer to the Solution Link on Github.
It is one of the most basic problems in backtracking. Let’s assume that there are n elements. Total number of permutations is n!. The crux of the problem is that, we have place given n numbers in n different positions. Let’s assume, we are constructing one permutation and we have placed k elements in first k positions. We have to place rest of the n-k elements at the n-k positions. For that, we can do
We place (k+1)th element at (k+1)th position in an ongoing permutation.
Given we have to write a single threaded application, we would start processing (n-k-1) elements as next step. This requires recursion.
We need to end the recursion. Otherwise, it would lead to Stack overflow. We would stop it when number of elements in the ongoing permutation equals to the total number of elements.
Why it is a backtracking problem?
Because, after we finish constructing a permutation, we have to construct next permutation. Let’s assume, we have constructed one permutation. A is placed at position k, and B is placed at position k+1. In next permutation, B will be placed at k, and A will be placed at k+1. Hence, we need to remove A from k, and then add B at k. To accomplish this, we require backtracking.
Will we not generate same permutation repeatedly, if we keep on iterating over the elements?
Valid question. The answer is no, because
We are tracking if a number already exists or not (code). Hence, we will not place the same element again.
We will always end the recursion when number of elements in the permutation is equal to number of given elements.
The loop in code will always traverse n number times and it would not repeat.
Yes, missing amny of this, would lead to infinite recursion.
Complexities
Time Complexities
The time complexity of this problem will have two parts
How many permutations we have to generate? - O(n!)
How many times we have to recurse down for each permutation? - O(n)
Total Complexity: O(n.n!)
Other Notes
Recursion is perfect for this kind of problems because one part of the problem is solved, we need to solve other part.
To improve run time, we can use multi threaded approach. We can spawn new threads for each level of recursion to increase parallel execution. However, it would mean spawing n! threads. That might be impractical. It would only reduce actual duration of the execution. The theoretical time complexity will remain same - O(n.n!).
Probably, we can fork n thread for first couple of level of recursion. It would provide a good balance.
Please visit this page to see the problems I have solved and my analysis.