Permutations — Interview Guide

• Swap-based backtracking produces permutations in place with O(n) extra space for the recursion.
• Pick-based backtracking (used/unused set) is more intuitive but uses more memory.
• For duplicates, sort and skip a duplicate when the identical previous element was not used in this branch.

def permute(nums):
    res = []
    def bt(first):
        if first == len(nums):
            res.append(nums[:]); return
        for i in range(first, len(nums)):
            nums[first], nums[i] = nums[i], nums[first]
            bt(first + 1)
            nums[first], nums[i] = nums[i], nums[first]
    bt(0)
    return res

• Permutations II: input has duplicates; return unique permutations only.
• Return the next lexicographic permutation in place.
• Generate the k-th permutation directly without enumerating all (factorial number system).