Generating Subsets with Duplicates

In our last session, we developed a backtracking template to generate all subsets of a set with unique elements. We established the core "include/exclude" decision-making process, which formed the backbone of our recursive algorithm. Today, we'll build directly on that foundation to tackle a common and important variation of this problem.

Our objective for this lesson is to modify the subset generation logic to handle duplicates and avoid duplicate results. When an input array like [1, 2, 2] is provided, a naive application of our previous algorithm would produce [1, 2] twice, which is incorrect. We'll refine our backtracking strategy to intelligently prune the search space and ensure every subset in our output is unique.

The Problem: Where Do Duplicate Subsets Come From?

Let's begin by understanding precisely why our existing "include/exclude" algorithm fails when duplicates are present. Consider the input nums = [1, 2, 2]. If we treat the two 2s as distinct entities (say, 2a and 2b), our decision tree from the last lesson would explore these two paths, among others:

1. Path A: Include 1, include 2a, exclude 2b. Resulting subset: [1, 2].
2. Path B: Include 1, exclude 2a, include 2b. Resulting subset: [1, 2].

Since 2a and 2b are both just the number 2, these two distinct paths in our decision tree produce the exact same final subset. This redundancy is what we need to eliminate.

The following diagram visualizes this exact scenario for nums = [1, 2, 2]. The red edges represent choices that lead to duplicate subsets that have already been generated through another path.

A simple but inefficient solution would be to generate all $2^n$ subsets, including duplicates, and then filter them using a hash set. While this works, it's a brute-force approach that incurs significant overhead. A more elegant solution modifies the backtracking logic itself to avoid ever generating these duplicates in the first place. This is the kind of optimization interviewers look for.

The Solution: Sort and Skip

The canonical approach to solving this problem involves a two-step strategy:

1. Sort the input array. This is a critical first step. By sorting nums, we ensure that all duplicate elements are grouped together (e.g., [1, 2, 2, 2, 3]). This makes them easy to identify and handle as a contiguous block.
2. Modify the decision logic. We introduce a new rule to our backtracking function: If we decide to not include an element nums[i], we must also skip all of its subsequent duplicates.

Let's unpack the intuition behind this rule. The AlgoMonster article provides a great explanation.

The NeetCode video below offers a superb visual demonstration of this concept. It shows the decision tree before and after applying the "sort and skip" logic, making the reason for the rule very clear.

To summarize the logic: The branch where we include nums[i] will be responsible for generating all unique subsets that contain nums[i]. Therefore, the branch where we exclude nums[i] should be responsible for generating subsets that do not contain nums[i] or any of its identical duplicates that follow. By skipping all subsequent duplicates in the "exclude" path, we cleanly partition the problem and avoid redundant work.

Modifying Our Backtracking Template

Now, let's adapt the Python code from our previous lesson. The changes are surprisingly minimal. We'll use the "include first, then exclude" structure, which makes the "skip" logic very clean.

Here's the template from last time:

# Previous lesson template
def subsets(nums):
    result = []
    current_subset = []

    def backtrack(index):
        if index >= len(nums):
            result.append(list(current_subset))
            return
        



        # Include nums[index]
        current_subset.append(nums[index])
        backtrack(index + 1)
        current_subset.pop() # Backtrack




        # Exclude nums[index]
        backtrack(index + 1)

    backtrack(0)
    return result

And here is the modified version for handling duplicates:

# Modified template for duplicates
def subsetsWithDup(nums):
    result = []
    current_subset = []
    nums.sort()  # Step 1: Sort the array

    def backtrack(index):
        if index == len(nums):
            result.append(list(current_subset))
            return




        # --- All subsets that INCLUDE nums[index] ---
        current_subset.append(nums[index])
        backtrack(index + 1)
        current_subset.pop() # Backtrack




        # --- All subsets that DO NOT INCLUDE nums[index] ---
        # Step 2: Skip duplicates before the next recursive call
        next_index = index + 1
        while next_index < len(nums) and nums[next_index] == nums[index]:
            next_index += 1
        backtrack(next_index)

    backtrack(0)
    return result

Notice the key differences:

1. We added nums.sort().
2. The "exclude" branch is no longer a simple backtrack(index + 1). Instead, it finds the index of the next unique element and jumps directly to it.

The following resources provide a complete implementation and code walkthrough.

An Alternative Backtracking Pattern

The "include/exclude" pattern is just one way to structure a backtracking solution. Another very common and powerful pattern builds subsets by iterating through the available choices at each step. This is particularly elegant for combination and permutation problems.

For subsetsWithDup, the logic is as follows:

1. At each step in the recursion (backtrack(start, current_subset)), first add the current_subset to the results. This captures subsets of all lengths.
2. Then, loop from the start index to the end of the array. In each iteration, you'll add nums[i] to current_subset and make a recursive call backtrack(i + 1, ...).
3. The duplicate-handling rule is applied inside this loop: if the current element nums[i] is the same as the previous one nums[i-1], and we are not at the very beginning of our loop (i > start), we skip it.

This i > start condition is subtle but vital. It ensures that we use a duplicate element the first time we see it in the loop (when i == start), but skip all subsequent occurrences of it at the same level of recursion.

This alternative style is explained visually in the following video. Seeing it animated in a recursion tree can greatly clarify how it works.

Both patterns are valid and will produce the correct result. Familiarity with both will make you a more flexible problem-solver, as some problems may map more naturally to one structure over the other.

Complexity Analysis

• Time Complexity: $O(n\cdot 2^n)$.

  • The nums.sort() call takes $O(n\log n)$.
  • In the worst-case scenario (an array with no duplicates), the backtracking function still explores $2^n$ paths to generate $2^n$ subsets.
  • Copying each subset into the result list takes up to $O(n)$ time.
  • Therefore, the overall complexity is dominated by the subset generation, resulting in $O(n\cdot 2^n)$.

• Space Complexity: $O(n)$.

  • This excludes the output list. The space is determined by the maximum depth of the recursion call stack, which is $n$. The current_subset also holds at most $n$ elements.

Conclusion

In this lesson, you've leveled up your backtracking skills by learning how to handle a crucial constraint: duplicate inputs. You saw that a simple "brute-force and filter" approach is suboptimal and that the efficient solution involves modifying the search algorithm itself.

Key Takeaways:

• The Problem: Duplicates in the input can cause different paths in the decision tree to generate identical subsets.
• The Strategy: The standard solution is to sort the input array first, which groups duplicates together.
• The Logic: You then modify the backtracking recursion to skip redundant computations.
  • In the "include/exclude" pattern, when you decide to exclude nums[i], you must advance your index past all identical adjacent elements.
  • In the "iterative choice" pattern, you use a loop at each recursive level and skip any element that is the same as its predecessor at that same level.
• Pattern Recognition: You are now familiar with two powerful backtracking templates for subset and combination problems.

In our next lesson, we will continue exploring the backtracking module by generating combinations of k elements from a set. This will add a new constraint—the size of the final set—which will require us to adapt our backtracking template once more.