Hints — p36 Permutations

Hint 1. “Enumerate all” → backtracking. Choose / recurse / un-choose.

Hint 2. You need to know which elements are already in the current path. A used = [False] * n array works.

Hint 3. Skeleton:

def backtrack(path):
    if len(path) == n:
        result.append(path[:])   # SNAPSHOT — the list mutates after we return
        return
    for i in range(n):
        if used[i]: continue
        used[i] = True; path.append(nums[i])
        backtrack(path)
        path.pop(); used[i] = False

Hint 4. Why path[:] (snapshot) and not path? Because we path.pop() after the recursive call — by the end, path == []. If you stored the reference, every result entry would point to the same empty list.

Hint 5. LC 47 (duplicates): sort the input, and in the loop add:

if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue

This produces each unique permutation exactly once. The not used[i-1] is the subtle part — it ensures we only consume equal values in left-to-right order.

If still stuck: see solution.py.