1. Problem Statement (Simple Explanation):
You’re given an array nums of distinct integers.
You must return all possible permutations of nums (all possible orderings).
The answer can be returned in any order.
2. Examples:
Example 1:
Input: nums = [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Example 2:
Input: nums = [0,1]
Output:
[
[0,1],
[1,0]
]
Example 3:
Input: nums = [1]
Output:
[
[1]
]
3. Approach – Backtracking (DFS):
This is a classic permutations problem.
Intuition:
We build permutations one position at a time:
At each step, we choose one of the remaining unused numbers to place next.
We continue until we have used all numbers → one complete permutation.
Then we backtrack and try another choice.
Since all integers in nums are distinct, we don’t need special duplicate handling.
Two common implementations:
Using a used[] boolean array and a current list.
Doing in-place swapping in nums.
Here I’ll use the used[] + current variant (very clear), and you can mention swap-variant as a note.
Algorithm:
Have:
result – list of all permutations.
current – current permutation being built.
used[i] – whether nums[i] is already in current.
Define backtrack():
If len(current) == len(nums):
Add a copy of current to result.
Return.
Else:
For each index i from 0 to n-1:
If used[i] is false:
Mark used[i] = true.
Append nums[i] to current.
Recurse: backtrack().
Backtrack:
Pop last from current.
Set used[i] = false.
Call backtrack() initially with empty current.
Pseudo-code:
Let n = len(nums):
There are n! permutations.
Each permutation of length n is built step-by-step:
Time: O(n*n!) (n permutations, each copy of length n)
Space:
O(n) recursion depth + O(n) for used and current
O(n) auxiliary (excluding output)
n ≤ 6 → 6! = 720 permutations → very manageable.
4. Java code:
6. C++ code:
7. Python code:
8. JavaScript code:
Comments
Post a Comment