90. Subsets II

Medium

Problem Description

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

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

Examples

Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:
Input: nums = [0]
Output: [[],[0]]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def subsetsWithDup(nums: List[int]) -> List[List[int]]:
    def backtrack(start: int, curr: List[int]):
        result.append(curr[:])
        
        for i in range(start, len(nums)):
            # Skip duplicates
            if i > start and nums[i] == nums[i-1]:
                continue
            curr.append(nums[i])
            backtrack(i + 1, curr)
            curr.pop()
    
    result = []
    nums.sort()  # Sort to handle duplicates
    backtrack(0, [])
    return result

Java Solution


class Solution {
    private List> result;
    private int[] nums;
    
    public List> subsetsWithDup(int[] nums) {
        result = new ArrayList<>();
        this.nums = nums;
        Arrays.sort(nums);  // Sort to handle duplicates
        backtrack(0, new ArrayList<>());
        return result;
    }
    
    private void backtrack(int start, List curr) {
        result.add(new ArrayList<>(curr));
        
        for (int i = start; i < nums.length; i++) {
            // Skip duplicates
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            curr.add(nums[i]);
            backtrack(i + 1, curr);
            curr.remove(curr.size() - 1);
        }
    }
}

C++ Solution


class Solution {
private:
    vector> result;
    vector nums;
    
    void backtrack(int start, vector& curr) {
        result.push_back(curr);
        
        for (int i = start; i < nums.size(); i++) {
            // Skip duplicates
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            curr.push_back(nums[i]);
            backtrack(i + 1, curr);
            curr.pop_back();
        }
    }
    
public:
    vector> subsetsWithDup(vector& nums) {
        this->nums = nums;
        sort(nums.begin(), nums.end());  // Sort to handle duplicates
        vector curr;
        backtrack(0, curr);
        return result;
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    const result = [];
    nums.sort((a, b) => a - b);  // Sort to handle duplicates
    
    const backtrack = (start, curr) => {
        result.push([...curr]);
        
        for (let i = start; i < nums.length; i++) {
            // Skip duplicates
            if (i > start && nums[i] === nums[i-1]) {
                continue;
            }
            curr.push(nums[i]);
            backtrack(i + 1, curr);
            curr.pop();
        }
    };
    
    backtrack(0, []);
    return result;
};

C# Solution


public class Solution {
    private IList> result;
    private int[] nums;
    
    public IList> SubsetsWithDup(int[] nums) {
        result = new List>();
        this.nums = nums;
        Array.Sort(nums);  // Sort to handle duplicates
        Backtrack(0, new List());
        return result;
    }
    
    private void Backtrack(int start, List curr) {
        result.Add(new List(curr));
        
        for (int i = start; i < nums.Length; i++) {
            // Skip duplicates
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            curr.Add(nums[i]);
            Backtrack(i + 1, curr);
            curr.RemoveAt(curr.Count - 1);
        }
    }
}

Complexity Analysis

Solution Explanation

This solution uses backtracking with duplicate handling:

Key points: