Generating Subsets using Backtracking

Subset generation via recursion mirrors binary expansion: at each index include or exclude; leaves are all 2^n subsets for distinct elements.

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)

For duplicates, sort first and skip equal neighbors at the same depth to avoid duplicate subsets—classic pattern.

Try this in Python

def subsets_dup(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res: list[list[int]] = []

    def dfs(i: int, path: list[int]) -> None:
        if i == len(nums):
            res.append(path.copy())
            return
        path.append(nums[i])
        dfs(i + 1, path)
        path.pop()
        while i + 1 < len(nums) and nums[i + 1] == nums[i]:
            i += 1
        dfs(i + 1, path)

    dfs(0, [])
    return res


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

Common mistakes

• Off-by-one causing empty extra subset at start if you mishandle initial call.
• Forgetting to copy path when storing results.

Key takeaways

• Iterative bitmask version good to know, but DFS is clearer in interviews.
• Use path.copy() or path[:] when appending to answer list.