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);

Moving Towards the Optimal Approach

Notice:

nums = [1,2,2]

After sorting:

[1,2,2]

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

At the same recursion level:

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

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);
        }
    }
}

Dry Run

Input

nums = [1,2,2]

After Sorting

[1,2,2]

Recursion Tree

[]

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

Output

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

Why Sorting Helps?

Sorting places duplicates together:

2 2

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;

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

推荐订阅源

DEV Community