Subsets and Permutations

Mastering subset and permutation problems is a critical rite of passage for any software engineer preparing for technical interviews. These problems are not just abstract puzzles; they test your fundamental ability to think recursively, manage state, and design efficient algorithms for generating combinatorial possibilities—a skill directly applicable to tasks like feature flagging, data sampling, and search space exploration. By understanding the core backtracking patterns, you transform intimidating problems into structured, solvable templates.

The Backtracking Mindset

At its heart, backtracking is a general algorithmic technique for finding all solutions by building candidates incrementally and abandoning a candidate ("backtracking") as soon as it is determined it cannot lead to a valid solution. Think of it as a systematic way to explore a decision tree, where each node represents a partial candidate. For generation problems like subsets and permutations, we explore every path in this tree. The key is to define three things: the state (the current partial solution), the choices you can make at this point, and the constraints that tell you when a path is dead-ended. This framework turns a vague problem into a clear recursive procedure where you make a choice, explore the consequences recursively, and then unmake the choice to try the next one.

Generating All Subsets

The subset problem asks: given a set of distinct integers, return all possible subsets (the power set). The core insight is that for each element, you have a binary choice: include it in the current subset or exclude it. A backtracking algorithm implements this as a depth-first traversal of a binary tree.

Consider the input nums = [1,2,3]. You start with an empty subset []. At the first level, for element 1, you have two branches: include 1 or exclude it. This process repeats for 2 and 3 at subsequent levels. The recursion ends when you've made a decision for every element in the input array, at which point the current state is a complete subset to be saved.

Here is the standard backtracking template for subsets:

def subsets(nums):
    res = []
    def backtrack(start, path):
        # Append a copy of the current path (a valid subset)
        res.append(path[:])
        # Explore further elements
        for i in range(start, len(nums)):
            # Make a choice: include nums[i]
            path.append(nums[i])
            # Recurse with the next starting index
            backtrack(i + 1, path)
            # Undo the choice (backtrack)
            path.pop()
    backtrack(0, [])
    return res

The start parameter is crucial. It ensures we only consider elements ahead of our current position, which prevents duplicates like [1,2] and [2,1] from appearing, as they represent the same subset. The order of generation is effectively lexicographic. The time complexity is $O(2^n\ast n)$, because there are $2^n$ subsets and, in the worst case, we copy a path of length $n$ each time.

Generating All Permutations

While subsets are about selection, permutations are about arrangement. The problem: given a list of distinct elements, return all possible orderings. The decision tree is now an n-ary tree where the choices at each level are all elements not yet used in the current path. The classic approach is to swap elements in-place to build permutations.

The algorithm works by fixing one element at a time at a given index. For nums = [1,2,3], you start at index 0. You swap 1 with itself (and later with 2 and 3), fixing the first position. Then you recursively do the same starting from index 1, and so on. When the fixing index reaches the end of the list, you have a complete permutation.

def permute(nums):
    res = []
    def backtrack(first):
        # If all indices are fixed, we have a complete permutation
        if first == len(nums):
            res.append(nums[:])
            return
        # Place each unused element at position 'first'
        for i in range(first, len(nums)):
            # Swap: place nums[i] at the current 'first' index
            nums[first], nums[i] = nums[i], nums[first]
            # Recurse to fix the next position
            backtrack(first + 1)
            # Undo the swap (backtrack)
            nums[first], nums[i] = nums[i], nums[first]
    backtrack(0)
    return res

This in-place swapping method is elegant and space-efficient, as it uses the input array to track the current state. The time complexity is $O(n!\ast n)$, as there are $n!$ permutations and we copy the array of length $n$ for each result. A common alternative uses a used boolean array and a path list to track state explicitly, which can be more intuitive for some and is necessary for handling duplicates.

Handling Duplicates in the Input

Real-world data often contains duplicates, and generating unique subsets or permutations becomes more challenging. Simply using the previous algorithms will produce duplicate results. The strategy to handle duplicates universally involves sorting the input array first. This allows us to "skip" over duplicate elements during our choice-making step, but the logic differs slightly between subsets and permutations.

For subsets with duplicates, after sorting, you skip choosing the same element at the same decision level. In the backtrack function's loop:

for i in range(start, len(nums)):
    # Skip duplicates at this decision level
    if i > start and nums[i] == nums[i-1]:
        continue
    path.append(nums[i])
    backtrack(i + 1, path)
    path.pop()

The condition i > start is key. It ensures we skip a duplicate element only when it is not the first element we are considering at this new level of recursion. This prevents the generation of duplicate subsets like [1,2] from input [1,2,2].

For permutations with duplicates, after sorting, you skip swapping an element into the first position if an identical element has already been placed there in this loop. You use a set (or check against the previous value) to track used elements at the current swap level:

for i in range(first, len(nums)):
    # Skip if we've already placed an identical element at 'first'
    if i > first and nums[i] == nums[i-1]:
        continue
    nums[first], nums[i] = nums[i], nums[first]
    backtrack(first + 1)
    nums[first], nums[i] = nums[i], nums[first]

The logic ensures that for a run of identical values, only one gets to be the leading element at a given recursive depth, guaranteeing unique permutations.

Common Pitfalls

1. Modifying the State Incorrectly During Backtracking: The most frequent error is forgetting to "undo" the choice (the pop() or the second swap) after the recursive call. This corrupts the state for subsequent iterations in the loop. Always remember the pattern: make a choice, recurse, then unmake the choice. Visualizing the call stack can help cement this.

• Correction: Explicitly pair every state modification with its reversal. For subsets, every path.append() must have a corresponding path.pop(). For in-place permutations, every swap must be followed by an identical swap to restore the original order.

1. Creating Duplicate Results with Non-Distinct Input: Applying the standard subset or permutation algorithm to an array like [1,2,2] will yield multiple identical subsets or permutations, which is usually not the desired output.

• Correction: Always sort the array first. For subsets, skip an element in the for-loop if it is a duplicate of the previous element and i > start. For permutations, skip swapping in an element if an identical element has already been swapped to the current first index in this loop.

1. Confusing Subset and Permutation State Management: Using a start index to prevent re-use is essential for subsets but incorrect for the standard permutation swap method. Conversely, trying to generate permutations by making include/exclude choices without tracking order will fail.

• Correction: Internalize the decision model. Subsets use an inclusion/exclusion choice with a moving start index to prevent going backward. Permutations use a placement choice (which element goes in the next slot), requiring you to track used elements either via swapping or a used array.

1. Appending a Reference Instead of a Copy: When you append the current path or nums array to the result list, you are appending a reference. Since you continue to modify this object, all entries in your result will end up being the final, empty state.

• Correction: Always append a copy: res.append(path[:]) or res.append(nums[:]). This captures the state at that moment in time.

Summary

• Subsets and permutations are foundational backtracking problems that test your ability to generate all combinatorial possibilities by exploring a decision tree recursively.
• For subsets, the core choice is include/exclude for each element, managed with a path list and a start index to move forward and avoid duplicates.
• For permutations, the core choice is which unused element to place next, implemented elegantly via in-place swapping or explicitly with a used array and a path.
• Handling duplicates requires pre-sorting the input and implementing a skip rule within the choice loop to prevent generating identical results at the same decision level.
• Avoid common implementation errors by meticulously pairing state changes with their reversal, appending copies of your state to results, and applying the correct choice model (inclusion vs. placement) for the problem at hand.