Subsets II medium

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. Return the solution in any order.

Example 1

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

Example 2

Input: nums = [0] Output: [[],[0]]

Steps

1. Sort the input array: Sorting ensures that we can easily identify and skip duplicate subsets later.
2. Backtracking: Use a recursive backtracking approach to generate all possible subsets.
3. Maintain a current subset: During recursion, we build a subset incrementally.
4. Handle duplicates: When encountering a duplicate element, we skip it in the current iteration of recursion if it was already included in the current subset in the previous iteration. This is crucial for avoiding duplicate subsets.
5. Add to result: Once a complete subset is formed (we've reached the end of the input array), add it to the result set.

Explanation

The backtracking approach systematically explores all possible combinations of including or excluding each element from the input array. Sorting allows us to efficiently identify and avoid duplicate subsets. For example, if we have [1, 2, 2], after considering [1, 2], we don't need to separately consider [1, 2, 2] because it's just a duplicate. The skip condition in the code takes care of this.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<int>> SubsetsWithDup(int[] nums) {
        Array.Sort(nums); // Sort to handle duplicates efficiently
        IList<IList<int>> result = new List<IList<int>>();
        List<int> subset = new List<int>();
        Backtrack(nums, 0, subset, result);
        return result;
    }

    private void Backtrack(int[] nums, int index, List<int> subset, IList<IList<int>> result) {
        result.Add(new List<int>(subset)); // Add a copy of the current subset

        for (int i = index; i < nums.Length; i++) {
            // Skip duplicate elements in the same recursion level
            if (i > index && nums[i] == nums[i - 1]) continue; 

            subset.Add(nums[i]);
            Backtrack(nums, i + 1, subset, result); //Recursive call
            subset.RemoveAt(subset.Count - 1); // Backtrack: remove the last added element
        }
    }
}

Complexity

• Time Complexity: O(N * 2^N), where N is the length of the input array. This is because there are 2^N possible subsets, and for each subset, we might spend O(N) time to copy it (although the copying overhead is usually not significant).
• Space Complexity: O(N * 2^N) in the worst case to store all subsets, and O(N) for the recursive call stack. The space used by subset is relatively small compared to the space for storing the result.