Permutations

1def permute(nums):
2  result = []
3
4  def backtrack(current, used):
5    # Base case: permutation complete
6    if len(current) == len(nums):
7      result.append(current[:])
8      return
9
10    # Try each unused number
11    for i in range(len(nums)):
12      if i in used:
13        continue
14
15      # Choose nums[i]
16      current.append(nums[i])
17      used.add(i)
18      backtrack(current, used)
19
20      # Backtrack
21      current.pop()
22      used.remove(i)
23
24  backtrack([], set())
25  return result