Subsets II | Backtracking

Problem Statement

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution must not contain duplicate subsets.

Brute Force Intuition

Generate all possible subsets using the classic Pick / Not Pick recursion.

After generating every subset, store them in a Set to remove duplicates.

While this works, many duplicate subsets are generated unnecessarily and later filtered out.

Complexity

• Time Complexity: O(2ᴺ × N)
• Space Complexity: O(2ᴺ)

Brute Force Snippet

Set<List<Integer>> set = new HashSet<>();

generateAllSubsets();

return new ArrayList<>(set);

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Notice:

nums = [1,2,2]

Enter fullscreen mode Exit fullscreen mode

After sorting:

[1,2,2]

Enter fullscreen mode Exit fullscreen mode

If we start a subset with the first 2, we should not start another identical subset with the second 2 at the same recursion level.

Instead of generating duplicates and removing them later, we can simply skip duplicate choices while building subsets.

Pattern Recognition

Whenever you see:

• Generate all subsets
• Duplicates present
• Unique combinations required

Think:

Backtracking + Sorting + Duplicate Skipping

Key Observation

After sorting:

1 2 2

Enter fullscreen mode Exit fullscreen mode

At the same recursion level:

if(i != ind && nums[i] == nums[i - 1])
    continue;

Enter fullscreen mode Exit fullscreen mode

This ensures we only consider the first occurrence and skip duplicate starts.

Optimal Java Solution

import java.util.*;

class Solution {

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);

        List<List<Integer>> ans = new ArrayList<>();

        helper(0, nums, new ArrayList<>(), ans);

        return ans;
    }

    private void helper(int ind,
                        int[] nums,
                        List<Integer> ds,
                        List<List<Integer>> ans) {

        ans.add(new ArrayList<>(ds));

        for (int i = ind; i < nums.length; i++) {

            if (i != ind && nums[i] == nums[i - 1])
                continue;

            ds.add(nums[i]);

            helper(i + 1, nums, ds, ans);

            ds.remove(ds.size() - 1);
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

nums = [1,2,2]

Enter fullscreen mode Exit fullscreen mode

After Sorting

[1,2,2]

Enter fullscreen mode Exit fullscreen mode

Recursion Tree

[]

├── [1]
│   ├── [1,2]
│   │   └── [1,2,2]
│
├── [2]
│   └── [2,2]
│
└── Skip second 2

Enter fullscreen mode Exit fullscreen mode

Output

[]
[1]
[1,2]
[1,2,2]
[2]
[2,2]

Enter fullscreen mode Exit fullscreen mode

Why Sorting Helps?

Sorting places duplicates together:

2 2

Enter fullscreen mode Exit fullscreen mode

Now we can easily identify repeated choices and skip them.

Without sorting, duplicate detection becomes much harder.

The Most Important Line

if(i != ind && nums[i] == nums[i - 1])
    continue;

Enter fullscreen mode Exit fullscreen mode

Meaning:

If the current number is the same as the previous number and both belong to the same recursion level, skip it.

This prevents duplicate subsets from being generated.

Complexity Analysis

Metric Complexity Time Complexity O(2ᴺ × N) Space Complexity O(N)

Reason:

• Up to 2ᴺ subsets.
• Copying subsets takes O(N).
• Recursion depth is N.

Interview One-Liner

Sort the array and use backtracking. While generating subsets, skip duplicate elements at the same recursion level to avoid duplicate subsets.

Pattern Learned

Generate All Subsets
+
Duplicates Present
+
Unique Answers Needed

=> Sort First
=> Backtracking
=> Skip Duplicates

Enter fullscreen mode Exit fullscreen mode

Similar Problems

• Subsets II
• Combination Sum II
• Permutations II
• N-Queens Variations
• Unique Subsequences