Subsets II - Video Solutions

Problem Overview: Given an integer array that may contain duplicate values, generate all possible subsets (the power set) while ensuring the result does not contain duplicate subsets. The main challenge is handling repeated elements so the same subset is not generated multiple times.

Approach 1: Backtracking with Sorting (O(n·2^n) time, O(n) extra space)

This approach uses backtracking to explore every subset possibility while preventing duplicates during recursion. First, sort the array so duplicate elements appear next to each other. During the recursive DFS, iterate from the current index and build the subset step by step. When encountering a duplicate value at the same recursion depth, skip it using a condition like if (i > start && nums[i] == nums[i-1]) continue. This ensures the algorithm only uses the first occurrence of each duplicate at a given level. The recursion tree explores include/exclude decisions and builds subsets incrementally. Time complexity is O(n·2^n) because up to 2^n subsets are generated and each subset copy may cost O(n). Space complexity is O(n) for the recursion stack (excluding output). This is the most common and interview-friendly solution.

Approach 2: Iterative Subset Construction (O(n·2^n) time, O(n·2^n) space)

This method builds subsets iteratively instead of recursion. Start with a result list containing an empty subset. Sort the array first so duplicates can be detected. For each number, iterate through the existing subsets and append the current number to create new subsets. When the current number is a duplicate of the previous one, only extend the subsets that were added in the previous step instead of all subsets. Tracking the starting index of newly created subsets prevents duplicate combinations. This technique treats subset generation as incremental expansion of the result list. Time complexity remains O(n·2^n) because every element can double the number of subsets. Space complexity is O(n·2^n) since all subsets are stored explicitly.

Both solutions rely on sorting the input array, a common pattern when working with duplicates in array problems. Some implementations also demonstrate subset generation using bit manipulation, but handling duplicates with bit masks typically requires additional filtering and is less practical here.

Recommended for interviews: Backtracking with sorting is the expected solution. It clearly demonstrates recursion, pruning, and duplicate handling using sorted input. Interviewers often want to see how you avoid generating duplicate subsets instead of filtering them afterward. The iterative construction method is also valid and useful if you prefer non-recursive solutions, but the backtracking approach better demonstrates algorithmic reasoning.