Swap-Based Backtracking (Permutations)

Swap-based permutations fix elements by swapping i with j≥i each level—different recursion shape than “pick from remaining list”.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Restore swap after recursion symmetrically: swap(i,j); dfs(i+1); swap(i,j) to backtrack correctly.

Try this in Python

def permute_swap(nums: list[int]) -> list[list[int]]:
    res: list[list[int]] = []

    def dfs(i: int) -> None:
        if i == len(nums):
            res.append(nums.copy())
            return
        used = set()
        for j in range(i, len(nums)):
            if nums[j] in used:
                continue
            used.add(nums[j])
            nums[i], nums[j] = nums[j], nums[i]
            dfs(i + 1)
            nums[i], nums[j] = nums[j], nums[i]

    dfs(0)
    return res


print(permute_swap([1, 1, 2]))

Common mistakes

• Swapping wrong indices causing duplicates or skipped permutations.
• Mutating shared global array across tests.

Key takeaways

• Heaps algorithm for minimal swaps—advanced; know classic swap DFS for arrays.