\

Subsets Ii

Difficulty: N/A | Solved: December 20, 2025

Problem

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3] **Output:** [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0] **Output:** [[],[0]]

Brainstorming

Brute force

the idea is we will follow the choose explore and undo paradigm of backtracking but with the concept of include exclude

so at each index we will have an option to include the current index value in the subset or ignore it the base case would then be when we have exhausted all the elements in the current branch


nums = [1,2,3]
subsets = []

def generate_subsets(index,current_subset,nums):
	if index > len(nums) -1:
		subsets.append(list(current_subset))
		return 
	# include the current index
	current_subset.append(nums[index])
	# explore 
	generate_subsets(index+1, current_subset, nums)
	# undo
	current_subset.pop()


generate_subsets(0, [], nums)
print(subsets)

current subset = [1] gen_sub 0+1 = 1 current_subset = [1,2] gen_sub 1+1 = 2 current_subset = [1,2,3] gen_sub 2+1 = 2 return current_subset.pop() current_subset = [1,2]

Optimal Solution

  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-06 12:00) - (end:: 2025-12-06 12:20) Include vs. Exclude.

This decision process forms a binary tree of choices. Our recursive function will traverse this tree.

Question 2: Structuring the Recursion

Let’s design our recursive helper function. We need to keep track of our progress.

  • We need to know which element we are currently making a decision about.
  • We need to know what the subset we’re building on the current path looks like.

So, a good signature is findSubsets(index, current_subset).

Now, think about the flow inside this function. It has to model the two choices you just identified.

  1. The “Exclude” Path: If you decide to exclude nums[index], what happens to current_subset? And what is the next recursive step you need to take?
  2. The “Include” Path: If you decide to include nums[index], what are the three distinct actions you need to take in order? (Think “Choose, Explore, Undo”).

if index > len(nums) - 1 is a perfect way to describe it. A more common and slightly cleaner way to write the exact same condition is:
if index == len(nums):

This means you’ve just finished making a decision for the last element (at index = len(nums) - 1), and the next recursive call is for an index that’s out of bounds, signifying you’re done.

You’ve now defined all three essential components:

  1. The Base Case: When index == len(nums), add a copy of current_subset to the results.
  2. The “Exclude” Path: Call findSubsets(index + 1, current_subset).
  3. The “Include” Path: current_subset.append(…), then call findSubsets(index + 1, …), then current_subset.pop().

You have everything you need.


nums = [1,2,3]
subsets = []

def generate_subsets(index,current_subset,nums):
	if index > len(nums) -1:
		subsets.append(list(current_subset))
		return 
	# exclude the current index
	# explore the branch where the current index is not part of the subset
	generate_subsets(index+1, current_subset, nums)
	# include the current index num to the current_subset
	current_subset.append(nums[index])
	# explore the branch where the current index is part of the subset
	generate_subsets(index+1, current_subset, nums)
	
	# undo pop the last added value from the subset
	current_subset.pop()


generate_subsets(0, [], nums)
print(subsets)

Duplicate elements

The Problem with Duplicates:

Let’s take nums =` [1, 2, 2]. If we run our current algorithm, what will happen?

  • The first 2 (at index 1) will be treated as a completely separate element from the second 2 (at index 2).
  • The path “Include 1, Exclude first 2, Include second 2” will generate the subset `[1, 2].
  • The path “Include 1, Include first 2, Exclude second 2” will also generate the subset `[1, 2].
  • Our final result list will contain duplicates:` [ [1, 2], [1, 2], … ].

The Goal: We need a rule to prune the decision tree to avoid generating these duplicate subsets.

The Core Insight for Handling Duplicates:

The key is to decide on a consistent rule. A very common and effective rule is:
“If I have a group of duplicate numbers, I will only ever consider including them starting from the first one. If I have skipped (excluded) a number, I will then skip all of its identical siblings that appear after it.”

Let’s apply this to [1, 2, 2'] (I’ll mark the second 2 to make it clear).

  • Path “Include 1, Exclude 2”: We have now skipped the element 2. Our rule says we must now also skip all subsequent 2s. So, we must also skip 2’. This path correctly generates [1].

  • Path “Include 1, Include 2”: We have not skipped 2. So, when we get to 2’, we are free to make a choice.

    • Path “Include 1, Include 2, Exclude 2’”: Generates `[1, 2].
    • Path “Include 1, Include 2, Include 2’”: Generates `[1, 2, 2].

This successfully avoids generating` [1, 2] twice.

How to Implement this Rule:

  1. Sort the Input Array First. This is critical. Sorting brings all duplicate elements together, making them easy to identify. `[2, 1, 2] becomes [1, 2, 2].

  2. Add a Condition to Your “Include” Choice.

    • Inside your for loop (if using that pattern) or your recursive step (for include/exclude), before you make the “Include” choice for nums[i], you must check if it’s a duplicate that should be skipped.
    • The condition is: if i > index and nums[i] == nums[i-1]: continue
      • i > index: This ensures we are only applying this rule for choices within the current step, not the first element of the subproblem.
      • nums[i] == nums[i-1]: This checks if the current element is a duplicate of the one just before it.
      • Putting it together: This line says, “If this element is the same as the previous one, AND we are in a position where we have already processed (and skipped) the previous one in this loop, then we must also skip this one.”
nums = [1,2,2]
nums.sort() # sort so that all duplicates come together
all_subsets = []

def generate_duplicate_subsets(index, current_subset):
	if index == len(nums):
		all_subsets.append(list(current_subset))
		return 
	
	# the recursive step
	# exclude the current element
	generate_duplicate_subsets(index+1, current_subset)
	
	if nums[index] == nums[index-1]: # duplicate
		index = index +1 
		return
	else:
		current_subset.append(nums[index])
		generate_duplicate_subsets(index+1, current_subset)
		current_subset.pop()

generate_duplicate_subsets(0,[])
print(all_subsets)

This is a fantastic attempt to integrate the duplicate-handling logic into the include/exclude pattern you’re comfortable with. You’ve correctly identified the need to sort and the need for a check involving nums[index] == nums[index-1].

Let’s trace your code to see where the logic goes slightly astray. This will be a great debugging exercise.

The Main Problem: Your “undo” is not correctly matched with your “choices.”

Let’s trace nums = [1, 2, 2].

1. gds(0, []) (index=0, num=1)

  • Exclude 1: Calls gds(1, []).
    • 2. gds(1, []) (index=1, num=2)
      • Exclude 2: Calls gds(2, []).
        • 3. gds(2, []) (index=2, num=2)
          • Exclude 2: Calls gds(3, []).
            • Base Case: index=3. all_subsets.append([]). Returns. all_subsets is [[]].
          • Include 2:
            • Check nums[2] == nums[1]? 2 == 2. True.
            • index = index + 1 -> index becomes 3 (locally).
            • return. This is a problem. This return stops the pop() from ever being reached for any corresponding append. More importantly, it prunes the path [2] which we actually need.
      • Include 2:
        • Check nums[1] == nums[0]? 2 == 1. False.
        • current_subset.append(2). cs is [2].
        • Calls gds(2, [2]).
          • 4. gds(2, [2]) (index=2, num=2)
            • Exclude 2: Calls gds(3, [2]).
              • Base Case: index=3. all_subsets.append([2]). Returns. all_subsets is [[], [2]].
            • Include 2:
              • Check nums[2] == nums[1]? 2 == 2. True.
              • return. Problem again. This prunes the [2, 2] path.
        • current_subset.pop(). cs is back to [].
      • gds(1, []) returns.
  • Include 1:
    • … (similar logic will run here) …

Let’s analyze the core issues with your if/else for duplicates:

  1. Incorrect State for the Check: The check nums[index] == nums[index-1] happens after the “Exclude” call. At this point, you don’t know whether you are on a path where the previous duplicate was included or excluded. The rule should be: “Only skip this duplicate if the previous identical element was excluded.” Your current code can’t tell the difference.

  2. Premature return: The return inside your if duplicate: block is too aggressive. It prunes valid paths like [2, 2] and prevents the necessary pop() from happening, which will break the state for the rest of the recursion.

Let’s go back to the core rule:

“If I’m about to make a choice, and this choice is the same as the one I had just before, I should only make this choice if I also made the choice just before.”

This is hard to implement with the pure “Exclude/Include” structure. This is why the second backtracking pattern I showed you is more common for subset/combination problems, especially with duplicates.

Let’s try to fix your current structure first, though. How can we prevent the [1, 2] and [1, 2'] duplication?

The duplication happens because:

  • Path 1: Exclude 2, Include 2'
  • Path 2: Include 2, Exclude 2'

We need to make one of these paths illegal. The standard convention is to forbid Path 1. “If you exclude 2, you cannot then include its twin 2'.”

How can we pass this information down? It’s tricky. You’d need another parameter in your recursion, like previous_was_skipped. This gets complicated.

A simpler fix within the “Include/Exclude” pattern:

nums = [2,1,2]
all_subsets = []
def generate_duplicate_subsets(index, current_subset):
    if index == len(nums):
        all_subsets.append(list(current_subset))
        return 

    # --- INCLUDE PATH ---
    # First, try the path where we include the current number.
    current_subset.append(nums[index])
    generate_duplicate_subsets(index + 1, current_subset)
    current_subset.pop() # Undo

    # --- EXCLUDE PATH (with duplicate check) ---
    # Now, try the path where we skip the current number.
    # BUT, if we skip, we must skip ALL of its duplicates too.
    # Find the next index that is NOT a duplicate of the current one.
    next_index = index + 1
    while next_index < len(nums) and nums[next_index] == nums[index]:
        next_index += 1
    
    generate_duplicate_subsets(next_index, current_subset)

# Initial call
nums.sort()
generate_duplicate_subsets(0, [])
print(all_subsets)

This is one way to fix your pattern. When you choose to “Exclude” nums[index], you find the next available number that is different and recurse from there, effectively skipping all the duplicates in between.

(Prompt): Can you trace nums=[1,2,2] with this new logic? See how it avoids generating [1,2] twice. Start with the call generate_duplicate_subsets(0, []).

  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-06 12:22) - (end:: 2025-12-06 12:52)