L11. Subset Sum II | Leetcode | Recursion

Generating subsets from an array containing duplicate elements requires specialized duplicate-handling logic during recursion rather than relying on costly post-processing data structures like sets. This chapter covers how to build a clean, optimized backtracking solution to return all unique subsets in any order.

1. Problem Statement & The Duplicate Challenge

Given an integer array nums that may contain duplicate elements, our goal is to return all possible unique subsets (the power set). The solution set must not contain duplicate subsets, and the result can be returned in any order.

• Status Quo Comparison: In the basic Subset Sum I problem where elements are unique, an array of size $n$ always yields exactly $2^n$ subsets via the pick and non-pick technique.
• The Duplication Trap: If an array contains duplicate elements (e.g., [1, 2, 2]), simply running standard recursion generates duplicate subsets (e.g., generating [1, 2] twice from different indices).
• The Core Objective: Design the recursive exploration such that duplicate subsets are never generated in the first place, avoiding post-processing overhead.

2. Naive Approach vs. Optimized Backtracking

When first encountering this problem, a naive solution often comes to mind before optimizing:

3. Core Mental Model: Level-by-Level Generation

Instead of viewing recursion as a binary choice tree for every single element, visualize the recursion as building subsets incrementally by size level:

• Level 0 (Empty Set): Generates the size-0 null list [].
• Level 1: Generates all unique subsets of size 1 (e.g., [1], [2], [3]).
• Level 2: Generates all unique subsets of size 2 (e.g., [1, 2], [1, 3], [2, 2], [3, 3]).
• Level 3+: Continues expanding valid combinations until all unique subsets up to size $n$ are formed.

4. Why Sorting is Mandatory

Note: To effectively ignore duplicate subsets during recursion, you must sort the input array first.

Sorting ensures that identical elements are positioned adjacently in memory (e.g., grouping all 2s together, all 3s together). Without sorting, identical numbers would be scattered across random indices, making it impossible to check whether a duplicate is being redundantly picked at the current level.

5. The Duplicate Skipping Rule (Horizontal Iteration Logic)

When iterating through choices at any given recursive step, we decide whether to pick element nums[i].

• First-Time Rule: You are always allowed to pick the first occurrence of a number at the current recursion level, because it introduces a fresh unique branch.
• Duplicate Skip Rule: If i > index and nums[i] == nums[i - 1], we skip this iteration. It has already been processed by its identical twin at the same level.

Visualizing the Recursion Transition

6. Complete Flow Walkthrough

Let's trace how the recursive engine executes step-by-step for nums = [1, 2, 2]:

1. Initialization: Sort nums -> [1, 2, 2]. Initialize an empty list ds and an answer list of lists.
2. Initial Call: findSubsets(0, ds, nums, answer)
   • Immediately add a deep copy of ds ([]) to answer.
3. Loop from i = index to n - 1:
   • For i = 0 (nums[0] = 1):
     • Not a duplicate of a previous element at this level.
     • Add 1 to ds ([1]).
     • Recurse: findSubsets(1, [1], nums, answer) -> Adds [1] to answer.
     • Further branches pick 2, adding [1, 2] and [1, 2, 2].
     • Backtrack: remove 1 from ds.
   • For i = 1 (nums[1] = 2):
     • Add 2 to ds ([2]).
     • Recurse and build [2, 2].
     • Backtrack: remove 2 from ds.
   • For i = 2 (nums[2] = 2):
     • Check: i > index (2 > 1) and nums[2] == nums[1] (2 == 2).
     • Action: continue (Skip this duplicate branch entirely!).

7. Complete Java Implementation

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // Step 1: Sort the array to bring duplicates together
        Arrays.sort(nums);
        List<List<Integer>> answer = new ArrayList<>();
        findSubsets(0, nums, new ArrayList<>(), answer);
        return answer;
    }

    private void findSubsets(int index, int[] nums, List<Integer> ds, List<List<Integer>> answer) {
        // Every state reached is a valid unique subset; add a deep copy to answer
        answer.add(new ArrayList<>(ds));

        // Iterate through remaining choices
        for (int i = index; i < nums.length; i++) {
            // Skip duplicates at the same level of recursion
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            }

            // Pick the element
            ds.add(nums[i]);
            
            // Move to the next index
            findSubsets(i + 1, nums, ds, answer);
            
            // Backtrack: remove the element for subsequent iterations
            ds.remove(ds.size() - 1);
        }
    }
}

8. Complete C++ Implementation

#include <vector>
#include <algorithm>

class Solution {
private:
    void findSubsets(int index, std::vector<int>& nums, std::vector<int>& ds, std::vector<std::vector<int>>& answer) {
        // Store every generated subset
        answer.push_back(ds);

        for (int i = index; i < nums.size(); i++) {
            // Skip adjacent duplicates at the same recursion level
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            }

            // Pick element
            ds.push_back(nums[i]);
            
            // Recurse to next index
            findSubsets(i + 1, nums, ds, answer);
            
            // Backtrack
            ds.pop_back();
        }
    }

public:
    std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
        std::vector<std::vector<int>> answer;
        std::vector<int> ds;
        
        // Sort to group duplicates
        std::sort(nums.begin(), nums.end());
        
        findSubsets(0, nums, ds, answer);
        return answer;
    }
};

9. Complexity Analysis

• Time Complexity: $\mathcal{O}(2^n \cdot n)$
  • Generating all subsets takes $\mathcal{O}(2^n)$ recursive calls in the worst-case scenario (when all elements are unique).
  • Deep-copying each subset into the final answer data structure takes proportional time to its length, averaging $\mathcal{O}(n)$ per subset.
• Space Complexity (Auxiliary): $\mathcal{O}(n)$
  • The maximum depth of the recursion stack is bounded by $n$ (the length of the array).
• Space Complexity (Output Storage): $\mathcal{O}(2^n \cdot k)$ where $k$ is the average length of the subsets stored in the answer vector.

Summary and Key Takeaways

• Problem Definition: Subset Sum II requires generating all unique subsets from an array containing duplicate values without duplicate result sets.
• Initial Sorting is Non-Negotiable: Always sort the array (Arrays.sort() or std::sort()) as a prerequisite so duplicate elements are adjacent.
• Level-Based Expansion: Recursion naturally builds subsets by size levels—from size 0 (empty set) up to size $n$.
• Horizontal Duplicate Skipping: Use the condition if (i > index && nums[i] == nums[i - 1]) continue; to safely bypass redundant branches.
• First-Occurrence Allowance: The first instance of a number at any recursion level is always permitted; only subsequent identical duplicates are skipped.
• No Explicit Base Case Required: The for-loop boundary (i < nums.length) naturally terminates recursion when all elements have been evaluated.
• Efficient Backtracking: Modifying a single data structure (ds) via add/remove (or push_back/pop_back) avoids unnecessary object creation overhead during traversal.