Find all distinct subsets of a given set using BitMasking Approach

Given an array arr[] that may contain duplicates. The task is to return all possible subsets. Return only unique subsets and they can be in any order.

Note: The individual subsets should be sorted.

Examples: 

Input:  arr[] = [1, 2, 2]
Output:  [], [1], [2], [1, 2], [2, 2], [1, 2, 2]
Explanation: The total subsets of given set are - [], [1], [2], [2], [1, 2], [1, 2], [2, 2], [1, 2, 2]
Here [2] and [1, 2] are repeated twice so they are considered only once in the output

Input:  arr[] = [1, 2]
Output:  [], [1], [2], [1, 2]
Explanation: The total subsets of given set are - [], [1], [2], [1, 2]

Refer to Find all Unique Subsets of a given Set for other approaches. In this article, bit masking is used.

Prerequisite: Power Set

Approach:

The idea is to generate all possible subsets using bitmasking technique where each bit position in a number from 0 to 2^n-1 represents whether to include or exclude the corresponding element from the array. We first sort the array to ensure each subset is sorted when generated. For each number i from 0 to 2^n-1, we check each bit position - if the bit is set, we include the corresponding array element in the current subset. To handle duplicates, we store each generated subset in a set container which automatically eliminates duplicate subsets.

Step by step approach:

1. Sort the input array to ensure each subset is sorted.
2. Generate all numbers from 0 to 2^n-1, each representing a unique subset.
3. For each number, check each of its bits to decide element inclusion.
4. Store each generated subset in a set to eliminate duplicates.
5. Transfer all unique subsets from the set to the result vector.

Illustration :

S = [1, 2, 2]

The binary digits from 0 to 7 are

0 --> 000    --> number formed with no set bits                              --> [ ]
1 --> 001    --> number formed with set bit at position 0                --> [ 1 ]
2 --> 010    --> number formed with set bit at position 1                --> [ 2 ]
3 --> 011    --> number formed with set bit at position 0  and 1     --> [ 1 , 2 ]
4 --> 100    --> number formed with set bit at position 2                -->  [ 2 ]
5 --> 101    --> number formed with set bit at position 0 and 2      --> [ 1 , 2]
6 --> 110    --> number formed with set bit at position 1 and 2      --> [ 2 , 2]
7 --> 111    --> number formed with set bit at position 0 , 1 and 2  --> [1 , 2 , 2]

After removing duplicates final result will be [ ], [ 1 ], [ 2 ], [ 1 , 2 ], [ 2 , 2 ], [ 1 , 2 , 2]

// C++ program to Find all distinct subsets // of a given set using BitMasking Approach #include <bits/stdc++.h> using namespace std; vector<vector<int>> printUniqueSubsets(vector<int>& arr) {  int n = arr.size();  vector<vector<int>> res;  set<vector<int>> set;    // Sort the array to ensure sorted subsets  sort(arr.begin(), arr.end());    int total = 1 << n;    // Generate each subset using bitmasking  for (int i = 0; i < total; i++) {  vector<int> subset;    // Check each bit of i  for (int j = 0; j < n; j++) {    // If jth bit is set, include arr[j]   // in the current subset  if (i & (1 << j)) {  subset.push_back(arr[j]);  }  }    // Add the subset to set to handle duplicates  set.insert(subset);  }    // Add all unique subsets from set to result vector  for (auto it : set) {  res.push_back(it);  }    return res; } int main() {  vector<int> arr = {1, 2, 2};  vector<vector<int>> res = printUniqueSubsets(arr);  for (auto v: res) {  for (auto u: v) cout << u << " ";  cout << endl;  }  return 0; } 

// Java program to Find all distinct subsets // of a given set using BitMasking Approach import java.util.*; class GfG {  static ArrayList<ArrayList<Integer>> printUniqueSubsets(int[] arr) {  int n = arr.length;  ArrayList<ArrayList<Integer>> res = new ArrayList<>();  Set<ArrayList<Integer>> set = new HashSet<>();    // Sort the array to ensure sorted subsets  Arrays.sort(arr);    int total = 1 << n;    // Generate each subset using bitmasking  for (int i = 0; i < total; i++) {  ArrayList<Integer> subset = new ArrayList<>();    // Check each bit of i  for (int j = 0; j < n; j++) {    // If jth bit is set, include arr[j]   // in the current subset  if ((i & (1 << j)) != 0) {  subset.add(arr[j]);  }  }    // Add the subset to set to handle duplicates  set.add(subset);  }    // Add all unique subsets from set to result vector  for (ArrayList<Integer> subset : set) {  res.add(subset);  }    return res;  }  public static void main(String[] args) {  int[] arr = {1, 2, 2};  ArrayList<ArrayList<Integer>> res = printUniqueSubsets(arr);  for (ArrayList<Integer> subset : res) {  for (int num : subset) {  System.out.print(num + " ");  }  System.out.println();  }  } } 

# Python program to Find all distinct subsets # of a given set using BitMasking Approach def printUniqueSubsets(arr): n = len(arr) res = [] unique_subsets = set() # Sort the array to ensure sorted subsets arr.sort() total = 1 << n # Generate each subset using bitmasking for i in range(total): subset = [] # Check each bit of i for j in range(n): # If jth bit is set, include arr[j]  # in the current subset if i & (1 << j): subset.append(arr[j]) # Add the subset to set to handle duplicates unique_subsets.add(tuple(subset)) # Add all unique subsets from set to result vector for subset in unique_subsets: res.append(list(subset)) return res if __name__ == "__main__": arr = [1, 2, 2] res = printUniqueSubsets(arr) for subset in res: for num in subset: print(num, end=" ") print() 

// C# program to Find all distinct subsets // of a given set using BitMasking Approach using System; using System.Collections.Generic; using System.Linq; class GfG {  static List<List<int>> PrintUniqueSubsets(int[] arr) {  int n = arr.Length;  List<List<int>> res = new List<List<int>>();  HashSet<List<int>> set = new HashSet<List<int>>(new ListComparer());    // Sort the array to ensure sorted subsets  Array.Sort(arr);    int total = 1 << n;    // Generate each subset using bitmasking  for (int i = 0; i < total; i++) {  List<int> subset = new List<int>();    // Check each bit of i  for (int j = 0; j < n; j++) {    // If jth bit is set, include arr[j]   // in the current subset  if ((i & (1 << j)) != 0) {  subset.Add(arr[j]);  }  }    // Add the subset to set to handle duplicates  set.Add(subset);  }    // Add all unique subsets from set to result vector  foreach (List<int> subset in set) {  res.Add(subset);  }    return res;  }  class ListComparer : IEqualityComparer<List<int>> {  public bool Equals(List<int> x, List<int> y) {  return x.SequenceEqual(y);  }    public int GetHashCode(List<int> obj) {  int hash = 17;  foreach (int item in obj) {  hash = hash * 23 + item.GetHashCode();  }  return hash;  }  }  static void Main() {  int[] arr = {1, 2, 2};  List<List<int>> res = PrintUniqueSubsets(arr);  foreach (List<int> subset in res) {  foreach (int num in subset) {  Console.Write(num + " ");  }  Console.WriteLine();  }  } } 

// JavaScript program to Find all distinct subsets // of a given set using BitMasking Approach function printUniqueSubsets(arr) {  let n = arr.length;  let res = [];  let set = new Set();    // Sort the array to ensure sorted subsets  arr.sort((a, b) => a - b);    let total = 1 << n;    // Generate each subset using bitmasking  for (let i = 0; i < total; i++) {  let subset = [];    // Check each bit of i  for (let j = 0; j < n; j++) {    // If jth bit is set, include arr[j]   // in the current subset  if (i & (1 << j)) {  subset.push(arr[j]);  }  }    // Add the subset to set to handle duplicates  set.add(JSON.stringify(subset));  }    // Add all unique subsets from set to result vector  set.forEach(subsetStr => {  res.push(JSON.parse(subsetStr));  });    return res; } let arr = [1, 2, 2]; let res = printUniqueSubsets(arr); for (let subset of res) {  console.log(subset.join(" ")); } 

1 1 2 1 2 2 2 2 2 

Time Complexity: O(2^n * n)
Auxiliary Space: O(2^n * n)