Handling Duplicates in Recursion

Duplicates require sorting + skip logic or frequency counts to avoid generating the same combination in different orders.

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)

At each depth, skip consecutive equal values after the first branch that uses/skips the block—standard permutations II pattern.

Try this in Python

def perm_unique(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res: list[list[int]] = []
    used = [False] * len(nums)

    def dfs(path: list[int]) -> None:
        if len(path) == len(nums):
            res.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i] or (i and nums[i] == nums[i - 1] and not used[i - 1]):
                continue
            used[i] = True
            path.append(nums[i])
            dfs(path)
            path.pop()
            used[i] = False

    dfs([])
    return res


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

Common mistakes

• Skip logic that also removes valid first occurrences.
• Sorting mutates shared input across tests—copy first.

Key takeaways

• Use if i > start and nums[i] == nums[i-1]: continue only in appropriate include branches.
• Document invariant “first duplicate can be used only if previous used”.