The problem
Given an array nums of different integers, return every permutation — every ordering of all its elements — in any order.
Examples
01
- Input
nums = [1, 2, 3]
- Output
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
02
- Input
nums = [0, 1]
- Output
[[0, 1], [1, 0]]
03
- Input
nums = [1]
- Output
[[1]]
Constraints
- 1 ≤ nums.length ≤ 6
- −10 ≤ nums[i] ≤ 10
- All the numbers are different.
The idea
There are n choices for the first position, n − 1 for the second, and so on: n! (“n factorial”, n × (n − 1) × … × 1) orderings. For 3 numbers, 3 × 2 × 1 = 6.
Fill the positions left to right, in place. Positions before k are settled; everything from k on is still unused. For each unused element, swap it into position k, fill the rest, and swap it back — the undo that makes this backtracking.
- Time
- O(n · n!) — n! orderings, each copied
- Space
- O(n) besides the answer
Solution · every language run against every case
class Solution: def permute(self, nums: List[int]) -> List[List[int]]: out = [] def place(k): # positions before k are fixed; choose what goes at k if k == len(nums): out.append(nums[:]) return for i in range(k, len(nums)): nums[k], nums[i] = nums[i], nums[k] # bring nums[i] to position k place(k + 1) nums[k], nums[i] = nums[i], nums[k] # and put it back place(0) return out