Code: Find all unique subset of an array with duplicate elements using Recursion | DSA in C++ - Software Development PDF Download

Here's a code in C++ that uses recursion to find all unique subsets of an array with duplicate elements:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void findUniqueSubsets(vector<int>& nums, int index, vector<int>& current, vector<vector<int>>& subsets) {

    // Add the current subset to the result

    subsets.push_back(current);

    for (int i = index; i < nums.size(); i++) {

        // Skip duplicate elements

        if (i > index && nums[i] == nums[i - 1])

            continue;

        // Include the current element in the subset

        current.push_back(nums[i]);

        // Recursively generate subsets with the remaining elements

        findUniqueSubsets(nums, i + 1, current, subsets);

        // Exclude the current element from the subset (backtrack)

        current.pop_back();

    }

}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {

    vector<vector<int>> subsets;

    vector<int> current;

    sort(nums.begin(), nums.end());  // Sort the array to handle duplicates

    findUniqueSubsets(nums, 0, current, subsets);

    return subsets;

}

int main() {

    vector<int> nums = {1, 2, 2};

    vector<vector<int>> result = subsetsWithDup(nums);

    // Output the subsets

    for (const auto& subset : result) {

        cout << "[ ";

        for (const auto& num : subset) {

            cout << num << " ";

        }

        cout << "]" << endl;

    }

    return 0;

}

Output:

[ ]

[ 1 ]

[ 1 2 ]

[ 1 2 2 ]

[ 2 ]

[ 2 2 ]

Explanation:

• The 'findUniqueSubsets' function is the main recursive function that generates subsets. It takes four parameters:
  • 'nums' is the input array.
  • 'index' is the current index being considered.
  • 'current' is the current subset being formed.
  • 'subsets' is a reference to the vector that stores all the subsets.
• The function starts by adding the current subset to the 'subsets' vector.
• It then loops through the array starting from the 'index' and checks for duplicate elements. If a duplicate is found, it skips that element to avoid generating duplicate subsets.
• For each unique element, it includes the current element in the subset by adding it to the current vector.
• The function then recursively calls itself with the updated index and current vector to generate subsets with the remaining elements.
• After the recursive call returns, it excludes the current element from the subset (backtracks) by removing it from the 'current' vector.
• The 'subsetsWithDup' function initializes the 'subsets' vector and 'current' vector, sorts the input array to handle duplicates, and then calls 'findUniqueSubsets' with the initial values.
• Finally, in the 'main' function, we create an example array 'nums' with duplicate elements. We call 'subsetsWithDup' to get all the unique subsets and then print them out.

The code utilizes recursion and backtracking to generate all unique subsets. The sorting step is crucial to handling duplicates, as it allows us to skip duplicate elements during the generation process.