Subsets II

BacktrackingRecursion

20 min

Problem Statement

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

Example

Example 1:

Input: nums = [1,2,2]

[]

[1]

[1, 2]

[1, 2, 2]

[2]

[2, 2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Solution

This problem is a variation of the Subsets problem, with the added complexity of handling duplicate elements in the input array. To ensure the solution set does not contain duplicate subsets, we first sort the array. Then, during the backtracking process, we add a check to skip generating subsets from a number if it's the same as the one before it.

Algorithm Steps

Sort the input array `nums` to handle duplicates easily.
Define a recursive function `backtrack(start, currentSubset)`.
Add the `currentSubset` to our list of results.
Iterate from `start` to the end of the `nums` array.
- **Crucial step for duplicates:** If `i > start` and `nums[i]` is the same as `nums[i-1]`, skip this iteration to avoid duplicate subsets.
- Include `nums[i]` in `currentSubset`.
- Recursively call `backtrack(i + 1, currentSubset)`.
- Backtrack: remove `nums[i]` from `currentSubset`.
Initial call: `backtrack(0, [])`.

Subsets II Visualization

Step-by-step backtracking algorithm

Progress1 / 1

Ready to start the visualization

Input Array (sorted)

Current Subset

[]

Unique Subsets

No solutions found yet...

Subsets II Solution


class Solution:
    def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
        res = []
        nums.sort()

        def backtrack(i, subset):
            if i == len(nums):
                res.append(subset.copy())
                return

            # All subsets that include nums[i]
            subset.append(nums[i])
            backtrack(i + 1, subset)
            subset.pop()
            
            # All subsets that don't include nums[i]
            while i + 1 < len(nums) and nums[i] == nums[i+1]:
                i += 1
            backtrack(i + 1, subset)

        backtrack(0, [])
        return res