This problem requires generating all possible subsets (the power set) of an integer array that may contain duplicate elements. The solution must ensure that the resulting list of subsets contains no duplicates, although the subsets themselves may be returned in any order.

For example, given the input nums = [1, 2, 2], the valid output includes [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]. The length of the input array is constrained between 1 and 10, with element values ranging from -10 to 10.

Method 1: State Tracking Backtracking

To handle duplicates, we can borrow logic similar to permutation problems with repeated elements. First, the array must be sorted so that identical numbers are adjacent. As we build the subset recursively, we need to decide whether to include the current element.

If the current element is the same as the previous one (nums[i] == nums[i-1]), we must ensure we don't generate duplicate branches. We enforce a rule: a duplicate element can only be added to the current path if the previous identical element is also currently active in the path. If the previous identical element is not in the path, it means we are trying to start a new branch with a duplicate value, which would create a subset that has already been generated when we processed the earlier occurence.

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& data) {
        sort(data.begin(), data.end());
        int len = data.size();
        vector<vector<int>> result;
        vector<int> current;
        vector<bool> isActive(len, false);

        function<void(int)> backtrack = [&](int idx) {
            if (idx == len) {
                result.push_back(current);
                return;
            }

            // Logic for including the element
            // Condition: 
            // 1. It's the first element (idx == 0), OR
            // 2. It's different from the previous element, OR
            // 3. It's the same as previous, but previous is already in current path
            if (idx == 0 || data[idx] != data[idx - 1] || isActive[idx - 1]) {
                current.push_back(data[idx]);
                isActive[idx] = true;
                backtrack(idx + 1);
                
                // Backtrack: remove current element and reset status
                current.pop_back();
                isActive[idx] = false;
            }

            // Logic for excluding the element
            backtrack(idx + 1);
        };

        backtrack(0);
        return result;
    }
};

Method 2: Pruning the "Skip" Branch

An alternative approach visualizes the decision process as a binary tree: at each step, we either "select" the current number or "not select" it.

To prevent duplicates without an extra isActive array, we can optimize the "not select" branch. If we decide to skip the current number nums[i], we should immediately skip all subsequent numbers that are equal to nums[i]. This is because selecting a later duplicate while skipping an earlier one would result in the exact same subset as selecting the earlier one and skippping the later one. By moving the index past all duplicates in the "skip" branch, we eliminate these redundant paths.

#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& data) {
        std::sort(data.begin(), data.end());
        int n = data.size();
        vector<vector<int>> collections;
        vector<int> temp;

        function<void(int)> dfs = [&](int idx) {
            if (idx == n) {
                collections.push_back(temp);
                return;
            }

            // Branch 1: Include nums[idx]
            temp.push_back(data[idx]);
            dfs(idx + 1);
            temp.pop_back(); // Restore state

            // Branch 2: Exclude nums[idx]
            // If we exclude this value, we must skip all consecutive identical values
            // to avoid duplicate subsets (e.g., picking the 2nd '2' instead of the 1st).
            int nextIdx = idx + 1;
            while (nextIdx < n && data[nextIdx] == data[idx]) {
                nextIdx++;
            }
            dfs(nextIdx);
        };

        dfs(0);
        return collections;
    }
};