Description
Return every ordering of an array of distinct integers. Each result uses every input value exactly once, and result order does not matter.
Solution
def permute(nums):
result, path = [], []
used = [False] * len(nums)
def visit():
if len(path) == len(nums):
result.append(path.copy())
return
for i, value in enumerate(nums):
if not used[i]:
used[i] = True
path.append(value)
visit()
path.pop()
used[i] = False
visit()
return resultExamples
Example 1
- Input
[[1,2]]- Output
[[1,2],[2,1]]
There are two orders.
Example 2
- Input
[[7]]- Output
[[7]]
A single value has one ordering.
Example 3
- Input
[[1,2,3]]- Output
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Three distinct values have six permutations.
Approach
Backtrack through unused input positions. Append a selected value, mark its position used, recurse, then undo the choice. Copy complete paths into the output.
Time & space
O(n n!) time and O(n) auxiliary space excluding output, where n is the array length.