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],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

Example 2

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

Steps

1. Sort the input array: Sorting ensures that duplicate subsets are easily identified and avoided.

2. Backtracking Algorithm: We use a recursive backtracking approach. At each index i in the input array:

   • We have a choice: either include the element nums[i] in the current subset or exclude it.
   • We recursively explore both possibilities.
   • To avoid duplicates, we skip over consecutive duplicate elements when excluding them.

Explanation

The backtracking algorithm systematically explores all possible combinations of including or excluding each element. Sorting the array is crucial because it allows us to easily identify and skip duplicate elements. If we didn't skip duplicate elements when excluding them, we would generate duplicate subsets. For example, if we had [1, 2, 2] and didn't handle duplicates, we'd generate [1, 2], [1, 2] (different positions for the second 2).

Code

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> currentSubset;
        sort(nums.begin(), nums.end()); // Sort to handle duplicates easily
        findSubsets(nums, 0, currentSubset, result);
        return result;
    }

private:
    void findSubsets(const vector<int>& nums, int index, vector<int>& currentSubset, vector<vector<int>>& result) {
        result.push_back(currentSubset); // Add the current subset to the result

        for (int i = index; i < nums.size(); ++i) {
            // Skip consecutive duplicates when excluding
            if (i > index && nums[i] == nums[i - 1]) continue;

            currentSubset.push_back(nums[i]);
            findSubsets(nums, i + 1, currentSubset, result); // Explore including nums[i]
            currentSubset.pop_back(); // Backtrack: remove nums[i] for the next iteration
        }
    }
};

Complexity

• Time Complexity: O(N * 2^N), where N is the number of elements in nums. This is because there are 2^N possible subsets, and generating each subset takes O(N) time in the worst case (copying elements).

• Space Complexity: O(N * 2^N) in the worst case, to store all the subsets in the result vector. The recursive call stack also uses space, but it's at most O(N) due to the depth of recursion. The dominant space usage is the result vector.