Subsets II - Video Solutions

Problem Overview: Given an integer array that may contain duplicates, generate all possible subsets (the power set) while ensuring that the result does not contain duplicate subsets. The challenge is not generating subsets—it’s avoiding repeated combinations when the input contains duplicate values.

Approach 1: Backtracking with Sorting (Time: O(2^n), Space: O(n))

This approach uses backtracking to explore every subset while carefully skipping duplicates. Start by sorting the array so duplicate values appear next to each other. During the recursive DFS, iterate through elements starting from the current index and append each element to the current subset. If the current element is the same as the previous element and appears at the same recursion depth, skip it to prevent generating the same subset again. Each recursive call either includes an element or moves forward to explore new combinations.

The key insight is that sorting groups duplicates together, which makes it possible to skip redundant branches in the recursion tree. Without this check, duplicate subsets would appear multiple times. The recursion stack depth is at most n, and every valid subset is produced exactly once. Since the total number of subsets in the worst case is 2^n, the time complexity is O(2^n) and the auxiliary recursion space is O(n). This method is commonly used in subset and combination problems involving duplicates.

Approach 2: Iterative Subset Construction (Time: O(2^n), Space: O(2^n))

This approach builds subsets iteratively using an expanding result list. Start with a single empty subset. After sorting the array, iterate through each element and extend the existing subsets by adding the current number. The tricky part is handling duplicates. When the current element is the same as the previous one, only extend the subsets that were added during the previous step rather than all subsets. This prevents duplicate combinations from forming.

The algorithm maintains a boundary that marks where new subsets began in the previous iteration. When encountering a duplicate element, iteration starts from that boundary instead of from the beginning of the result list. Each step effectively doubles or partially expands the subset list. Because every subset is constructed exactly once, the time complexity remains O(2^n) with space O(2^n) for storing the result. This method works well when you prefer iterative logic over recursion and is still rooted in operations on an array.

Recommended for interviews: The backtracking approach with sorting is the most commonly expected solution. Interviewers want to see that you recognize duplicates as a pruning condition in the recursion tree. Writing the brute recursive structure first demonstrates understanding of subset generation, while adding the duplicate-skip condition shows mastery of backtracking patterns. The iterative method is a strong alternative when discussing different ways to construct the power set.