Subsets II - Practice Coding Problems

Subsets II - Problem

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.

Note: A subset is a selection of elements from the array, including the empty subset and the array itself.

Input & Output

Example 1 — Basic Case with Duplicates

$ Input: nums = [1,2,2]

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

💡 Note: The array contains duplicates. All unique subsets are: empty set, single elements [1] and [2], pairs [1,2] and [2,2], and the full array [1,2,2]. Note that [2] appears only once even though there are two 2s.

Example 2 — All Identical Elements

$ Input: nums = [4,4,4]

› Output: [[],[4],[4,4],[4,4,4]]

💡 Note: When all elements are identical, we get subsets of different lengths: empty, single element, pair, and triplet. No actual duplicates in the result.

Example 3 — No Duplicates

$ Input: nums = [1,2,3]

› Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

💡 Note: When there are no duplicates in input, this behaves like the regular Subsets problem, generating all 2^3 = 8 possible subsets.

Constraints

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10

Visualization

Tap to expand

Understanding the Visualization

Input

Array with duplicates: [1,2,2]

Process

Generate all unique subsets avoiding duplicates

Output

6 unique subsets (not 8 like regular subsets)

Key Takeaway

🎯 Key Insight: Sort first, then skip duplicates at the same recursion level to avoid duplicate subsets

Asked in

F Facebook 35 a Amazon 28 M Microsoft 22 G Google 18

The key insight is to sort the array first, then use backtracking while skipping duplicate elements at the same recursion level. Best approach is backtracking with duplicate skipping. Time: O(n × 2^n), Space: O(n × 2^n)

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation with Sorted Deduplication	O(n × 2^n)	O(1)	Sort array first, then use bit manipulation to generate subsets and skip duplicates efficiently
Backtracking with Duplicate Skipping	O(n × 2^n)	O(n × 2^n)	Sort array first, then use backtracking while skipping duplicate elements at same level
Generate All + Remove Duplicates	O(n × 2^n)	O(n × 2^n)	Generate all 2^n subsets, then filter out duplicates using a set

Bit Manipulation with Sorted Deduplication — Algorithm Steps

Sort array to group duplicate elements together
Use bit manipulation to generate all 2^n combinations
Skip invalid combinations where duplicates are not in consecutive order

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Group duplicates together: [1,2,2]

Check Patterns

Validate each bit pattern for duplicate rules

Valid Subsets

Only accept patterns where duplicates appear consecutively

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int** solution(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), compare);
    
    int maxSubsets = 1 << numsSize;
    int** result = (int**)malloc(maxSubsets * sizeof(int*));
    *returnColumnSizes = (int*)malloc(maxSubsets * sizeof(int));
    int resultSize = 0;
    
    for (int mask = 0; mask < (1 << numsSize); mask++) {
        // Check if this mask represents a valid subset
        int valid = 1;
        for (int i = 1; i < numsSize; i++) {
            // If current element is same as previous but previous is not selected
            // and current is selected, then skip this combination
            if (nums[i] == nums[i-1] && (mask & (1 << (i-1))) == 0 && (mask & (1 << i)) != 0) {
                valid = 0;
                break;
            }
        }
        
        if (valid) {
            int* subset = (int*)malloc(numsSize * sizeof(int));
            int subsetSize = 0;
            
            for (int i = 0; i < numsSize; i++) {
                if (mask & (1 << i)) {
                    subset[subsetSize++] = nums[i];
                }
            }
            
            result[resultSize] = subset;
            (*returnColumnSizes)[resultSize] = subsetSize;
            resultSize++;
        }
    }
    
    *returnSize = resultSize;
    return result;
}

int main() {
    // Simple input parsing
    int nums[10];
    int numsSize = 0;
    
    // Read array - simplified parsing
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char* token = strtok(line, "[,]");
    while (token != NULL && numsSize < 10) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(nums, numsSize, &returnSize, &returnColumnSizes);
    
    // Print result
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2^n)

Check each of 2^n bit patterns and validate each in O(n) time

⚠ Quadratic Growth

Space Complexity

O(1)

Only use constant extra space for bit manipulation (excluding output)

✓ Linear Space

185.0K Views

Medium Frequency

~15 min Avg. Time

3.3K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation with Sorted Deduplication — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler