Permutations
The key idea
Build each permutation one slot at a time. At every slot try every number not yet used, recurse, then undo that choice (backtrack) so the next branch can reuse it. The
used set is what keeps each number to one appearance per permutation.Problem
Given an array nums of distinct integers, return all the possible permutations. You may return the answer in any order.
A permutation is an arrangement of nums that uses every element exactly once; the order of elements is what differs between permutations.
Constraints
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
numsare unique.
Examples
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]]
Complexity
Time: O(n * n!) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Backtracking problems
- Combination SumMEDIUM
- Combination Sum IIMEDIUM
- Combination Sum IIIMEDIUM
- CombinationsMEDIUM
- Generate ParenthesesMEDIUM
- Letter Combinations of a Phone NumberMEDIUM
- Matchsticks to SquareMEDIUM
- N-QueensHARD
- N-Queens IIHARD
- Non-decreasing SubsequencesMEDIUM
- Palindrome PartitioningMEDIUM
- Partition to K Equal Sum SubsetsMEDIUM