Medium Backtrack+Prune Backtracking
In plain English: Generate every possible ordering of a list of distinct numbers.
At each position, try every unused element. A set tracks what is used — when the path has n elements, you have a full permutation.
Prompt
Given a list of distinct integers, return all possible permutations.
Try to write it from scratch before scrolling down.
Solution
def permutations(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if i in used:
continue
used.add(i)
path.append(nums[i])
backtrack(path, used)
path.pop()
used.remove(i) # backtrack
backtrack([], set())
return result
# Test: permutations([1,2,3]) has 6 permutations