Find all Unique Subsets of a given Set
Given an array A[] of positive integers, print all the unique non-empty subsets of the array
Note: The set can not contain duplicate elements, so any repeated subset should be considered only once in the output.
Examples:
Input: A[] = {1, 5, 6}
Output: {{1}, {1, 5}, {1, 6}, {5}, {5, 6}, {6}, {1, 5, 6}}
Explanation: The number of all the non-empty possible subsets will be 2N-1.
Here it will be {1}, {1, 5}, {1, 6}, {5}, {5, 6}, {6} and {1, 5, 6}Input: A[] = {1, 2, 2}
Output: {{1}, {1, 2}, {1, 2, 2}, {2}, {2, 2}}
Intuition: The main idea to solve the problem is as follows:
This problem falls under the classic algorithm of “pick or don’t pick“.
In this problem, there are two choices of whether we want to include an element in the set or exclude it. For every choice, the element can be appended into the resultant array and then, using backtracking, we will exclude it. This way, the desired set will be generated.
The image shown below shows the choices for each element and how the resultant array is generated at the end of the recursion tree.
Approach 1 (Recursion):
Follow the given steps to solve the problem using the above approach:
- Iterate over the elements one by one.
- For each element, just pick the element and move ahead recursively and add the subset to the result.
- Then using backtracking, remove the element and continue finding the subsets and adding them to the result.
Below is the implementation for the above approach:
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Helper function to find all unique subsets
void findSubsets(vector<int>& v, int idx,
vector<int>& subset,
set<vector<int> >& result)
{
// If the current subset is not empty
// insert it into the result
if (!subset.empty())
result.insert(subset);
// Iterate over every element in the array
for (int j = idx; j < v.size(); j++) {
// Pick the element and move ahead
subset.push_back(v[j]);
findSubsets(v, j + 1, subset, result);
// Backtrack to drop the element
subset.pop_back();
}
}
// Function to return all unique subsets
vector<vector<int> > solve(vector<int>& v)
{
// To store the resulting subsets
set<vector<int> > result;
vector<int> subset;
// Helper function call
findSubsets(v, 0, subset, result);
vector<vector<int> > res;
for (auto v : result)
res.push_back(v);
return res;
}
// Driver code
int main()
{
vector<int> A = { 1, 2, 2 };
// Function call
vector<vector<int> > result = solve(A);
// Print all unique subsets
for (auto v : result) {
for (int i : v) {
cout << i << " ";
}
cout << "\n";
}
return 0;
}
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG {
// Helper function to find all unique subsets
static void findSubsets(List<Integer> v, int idx,
List<Integer> subset,
List<List<Integer> > result)
{
// If the current subset is not empty insert it into
// the result
if (!subset.isEmpty()) {
if (!result.contains(subset)) {
result.add(new ArrayList<>(subset));
}
}
// Iterate over every element in the array
for (int j = idx; j < v.size(); j++) {
// Pick the element and move ahead
subset.add(v.get(j));
findSubsets(v, j + 1, subset, result);
// Backtrack to drop the element
subset.remove(subset.size() - 1);
}
}
// Function to return all unique subsets
static List<List<Integer> > solve(List<Integer> v)
{
// To store the resulting subsets.
List<List<Integer> > result
= new ArrayList<List<Integer> >();
List<Integer> subset = new ArrayList<Integer>();
// Helper function call
findSubsets(v, 0, subset, result);
List<List<Integer> > res
= new ArrayList<List<Integer> >();
for (int i = 0; i < result.size(); i++) {
res.add(new ArrayList<>(result.get(i)));
}
return res;
}
public static void main(String[] args)
{
List<Integer> A = new ArrayList<Integer>();
A.add(1);
A.add(2);
A.add(2);
List<List<Integer> > result
= new ArrayList<List<Integer> >();
// Function call
result = solve(A);
// print all unique subsets
for (int i = 0; i < result.size(); i++) {
List<Integer> temp = result.get(i);
for (int j = 0; j < temp.size(); j++) {
System.out.print(temp.get(j) + " ");
}
System.out.println();
}
}
}
// This code is contributed by lokesh (lokeshmvs21).
// C# code to implement the approach
using System;
using System.Collections.Generic;
using System.Linq;
public class ListEqualityComparer<T>
: IEqualityComparer<List<T> > {
private readonly IEqualityComparer<T>
_itemEqualityComparer;
public ListEqualityComparer()
: this(null)
{
}
public ListEqualityComparer(
IEqualityComparer<T> itemEqualityComparer)
{
_itemEqualityComparer = itemEqualityComparer
?? EqualityComparer<T>.Default;
}
public static readonly ListEqualityComparer<T> Default
= new ListEqualityComparer<T>();
public bool Equals(List<T> x, List<T> y)
{
if (ReferenceEquals(x, y))
return true;
if (ReferenceEquals(x, null)
|| ReferenceEquals(y, null))
return false;
return x.Count == y.Count
&& !x.Except(y, _itemEqualityComparer).Any();
}
public int GetHashCode(List<T> list)
{
int hash = 17;
foreach(var itemHash in list
.Select(x => _itemEqualityComparer
.GetHashCode(x))
.OrderBy(h => h))
{
hash += 31 * itemHash;
}
return hash;
}
}
class Program {
// Helper function to find all unique subsets
static void findSubsets(List<int> v, int idx,
List<int> subset,
List<List<int> > result)
{
// If the current subset is not empty
// insert it into the result
if (subset.Count != 0) {
result.Add(new List<int>(subset));
}
// Iterate over every element in the array
for (int j = idx; j < v.Count; j++) {
// Pick the element and move ahead
subset.Add(v[j]);
findSubsets(v, j + 1, subset, result);
// Backtrack to drop the element
subset.RemoveAt(subset.Count - 1);
}
}
// Function to return all unique subsets
static List<List<int> > solve(List<int> v)
{
// To store the resulting subsets
List<List<int> > result = new List<List<int> >();
List<int> subset = new List<int>();
// Helper function call
findSubsets(v, 0, subset, result);
List<List<int> > newList
= result
.Distinct(
ListEqualityComparer<int>.Default)
.ToList();
return newList;
}
// Driver code
static void Main(string[] args)
{
List<int> A = new List<int>();
A.Add(1);
A.Add(2);
A.Add(2);
// Function call
List<List<int> > result = solve(A);
// Print all unique subsets
foreach(List<int> v in result)
{
foreach(int i in v) { Console.Write(i + " "); }
Console.WriteLine();
}
}
}
// This code is contributed by Tapesh(tapeshdua420)
// Javascript code to implement the approach
let result = new Set();
let subset = [];
// Helper function to find all unique subsets
function findSubsets(idx)
{
// If the current subset is not empty
// insert it into the result
if (subset.length > 0){
result.add(subset.join(""));
}
// Iterate over every element in the array
for (let j = idx; j < v.length; j++) {
// Pick the element and move ahead
subset.push(v[j]);
findSubsets(j + 1);
// Backtrack to drop the element
subset.pop();
}
}
// Function to return all unique subsets
function solve()
{
// To store the resulting subsets
// Helper function call
findSubsets(0);
let res = Array.from(result);
// console.log(res);
return res;
}
// Driver code
let v = [1, 2, 2];
// Function call
let rslt = solve(v);
// Print all unique subsets
for(let i = 0; i < rslt.length; i++){
let temp = "";
for(let j = 0; j < rslt[i].length; j++){
temp = temp + rslt[i][j] + " ";
}
console.log(temp);
}
// The code is contributed by Nidhi goel.
# Python code to implement the above approach
# Helper function to find all unique subsets
def findSubsets(v, idx, subset, result):
# If the current subset is not empty insert it into
# the result
if (len(subset) != 0):
if (subset not in result):
result.append(subset[:])
# Iterate over every element in the array
for j in range(idx, len(v)):
# Pick the element and move ahead
subset.append(v[j])
findSubsets(v, j + 1, subset, result)
# Backtrack to drop the element
subset.pop()
# Function to return all unique subsets
def solve(v):
# To store the resulting subsets.
result = []
subset = []
# Helper function call
findSubsets(v, 0, subset, result)
res = []
for i in range(len(result)):
res.append(list(result[i]))
return res
if __name__ == '__main__':
A = [1, 2, 2]
# Function Call
result = solve(A)
# print all unique subsets
for i in range(len(result)):
temp = result[i]
for j in range(len(temp)):
print(temp[j], end=" ")
print()
# This code is contributed by Tapesh(tapeshdua420)
Output
1 1 2 1 2 2 2 2 2
Time complexity: O(N * log(2N) * 2N) = O(N2 * 2N)
Auxiliary space: O(2N)
Approach 2 (Iterative Approach):
Follow the given steps to solve the problem using the above approach:
- Iterate through every number, and there are two choices:
- Either include the element, then add it into all subsets.
- Or exclude the element, then don’t do anything.
Below is the implementation for the above approach:
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return all unique subsets
vector<vector<int> > solve(vector<int>& v)
{
// To store the resulting subsets
set<vector<int> > res;
vector<int> subset;
vector<vector<int> > result;
// Insert it into the resultant vector
res.insert(subset);
// Iterate over all elements
for (int i = 0; i < v.size(); i++) {
int N = res.size();
for (auto it = res.begin();
it != res.end() and N > 0; it++) {
// Iterate through every subset
// generated till now and inset
// the current element in the
// end of it
subset = *it;
subset.push_back(v[i]);
result.push_back(subset);
N--;
}
res.insert(result.begin(), result.end());
result.clear();
}
for (auto u : res)
result.push_back(u);
return result;
}
// Driver code
int main()
{
vector<int> A = { 1, 2, 2 };
// Function call
vector<vector<int> > result = solve(A);
for (auto v : result) {
for (int i : v) {
cout << i << " ";
}
cout << "\n";
}
return 0;
}
// Java code to implement the approach
import java.util.*;
class GFG
{
// Function to return all unique subsets
public static List<List<Integer> >
solve(List<Integer> v)
{
// To store the resulting subsets
Set<List<Integer> > res = new HashSet<>();
List<Integer> subset = new ArrayList<>();
List<List<Integer> > result = new ArrayList<>();
// Insert it into the resultant vector
res.add(subset);
// Iterate over all elements
for (int i = 0; i < v.size(); i++) {
int N = res.size();
for (List<Integer> it : res) {
// Iterate through every subset
// generated till now and insert
// the current element in the
// end of it
subset = new ArrayList<>(it);
subset.add(v.get(i));
result.add(subset);
N--;
if (N == 0) {
break;
}
}
res.addAll(result);
result.clear();
}
return new ArrayList<>(res);
}
// Driver code
public static void main(String[] args)
{
List<Integer> A = Arrays.asList(1, 2, 2);
// Function call
List<List<Integer> > result = solve(A);
result.sort((x, y) -> {
for (int i = 0;
i < Math.min(x.size(), y.size()); i++) {
if (x.get(i) != y.get(i)) {
return x.get(i) - y.get(i);
}
}
return x.size() - y.size();
});
for (List<Integer> v : result) {
for (int i : v) {
System.out.print(i + " ");
}
System.out.println();
}
}
}
// This code is contributed by akashish__
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// Function to return all unique subsets
public static List<List<int>>
solve(List<int> v)
{
// To store the resulting subsets
HashSet<List<int>> res = new HashSet<List<int>>();
List<int> subset = new List<int>();
List<List<int>> result = new List<List<int>>();
// Insert it into the resultant vector
res.Add(subset);
// Iterate over all elements
for (int i = 0; i < v.Count(); i++)
{
int N = res.Count();
foreach (List<int> it in res)
{
// Iterate through every subset
// generated till now and insert
// the current element in the
// end of it
subset = new List<int>(it);
subset.Add(v[i]);
result.Add(subset);
N--;
if (N == 0)
{
break;
}
}
res.UnionWith(result);
result.Clear();
}
return res.ToList();
}
// Driver code
static void Main(string[] args)
{
List<int> A = new List<int> { 1, 2, 2 };
// Function call
List<List<int>> result = solve(A);
result.Sort((x, y) =>
{
for (int i = 0;
i < Math.Min(x.Count(), y.Count()); i++)
{
if (x[i] != y[i])
{
return x[i] - y[i];
}
}
return x.Count() - y.Count();
});
foreach (List<int> v in result)
{
foreach (int i in v)
{
Console.Write(i + " ");
}
Console.WriteLine();
}
}
}
function solve(v) {
// To store the resulting subsets
let res = new Set();
let subset = [];
let result = [];
// Insert it into the resultant set
res.add(subset.toString());
// Iterate over all elements
for (let i = 0; i < v.length; i++) {
let N = res.size;
for (let it of res) {
// Iterate through every subset generated till now and insert the current element in the end of it
let subset = it.split(",").map(Number);
subset.push(v[i]);
result.push(subset);
N--;
if (N == 0) {
break;
}
}
for (let x of result) {
res.add(x.toString());
}
result = [];
}
return Array.from(res).map((x) => x.split(",").map(Number));
}
// Driver code
let A = [1, 2, 2];
// Function call
let result = solve(A);
result.sort((x, y) => {
for (let i = 0; i < Math.min(x.length, y.length); i++) {
if (x[i] != y[i]) {
return x[i] - y[i];
}
}
return x.length - y.length;
});
result.forEach((v) => { let temp="";
v.forEach((i) => { if (i!=0){
temp = temp +i + " "; }
});
console.log(temp);
});
from typing import List
def solve(v: List[int]) -> List[List[int]]:
# To store the resulting subsets
res = set()
subset = []
result = []
# Insert an empty subset into the resultant set
res.add(tuple(subset))
# Iterate over all elements
for i in range(len(v)):
N = len(res)
for it in res:
# Iterate through every subset generated till now and insert the current element in the end of it
subset = list(it)
subset.append(v[i])
result.append(subset)
N -= 1
if N == 0:
break
res.update([tuple(x) for x in result])
result.clear()
return [list(x) for x in res]
# Driver code
if __name__ == '__main__':
A = [1, 2, 2]
# Function call
result = solve(A)
result.sort(key=lambda x: (len(x), x))
for v in result:
for i in v:
print(i, end=' ')
print()
Output
1 1 2 1 2 2 2 2 2
Time complexity: O(N2 * 2N)
Auxiliary space: O(2N)
Approach 3 (Bit Masking):
Prerequisite: Power Set
To solve the problem using the above approach, follow the idea below:
Represent all the numbers from 1 to 2N – 1 where N is the size of the subset in the binary format and the position for which the bits are set to be added to the array and then add that array into the result i.e to use a bit-mask pattern to generate all the combinations. For example,
Input: A = {1, 5, 6}, N = 3
Explanation: Hence we will check every number from 1 to 7 i.e.till 2n-1 = 23 – 1 = 7
1 => 001 => {6}
2 => 010 => {5}
3 => 011 => {5, 6}
4 => 100 => {1}
5 => 101 => {1, 6}
6 => 110 => {1, 5}
7 => 111 => {1, 5, 6}
Below is the implementation for the above approach:
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the unique subsets
vector<vector<int> > solve(vector<int>& v)
{
// To store the resulting subsets
set<vector<int> > res;
vector<int> subset;
int size = v.size();
// Finding 2^N
int N = 1 << size;
for (int i = 1; i < N; i++) {
int bit = i;
subset.clear();
int pos = 0;
while (bit) {
// If the bit is set inset
// it into the subset
if (bit & 1) {
subset.push_back(v[pos]);
}
pos++;
bit >>= 1;
}
res.insert(subset);
}
vector<vector<int> > result;
for (auto u : res)
result.push_back(u);
return result;
}
// Driver code
int main()
{
vector<int> A = { 1, 2, 2 };
// Function call
vector<vector<int> > result = solve(A);
for (auto v : result) {
for (int i : v) {
cout << i << " ";
}
cout << "\n";
}
return 0;
}
// Java code to implement the approach
import java.util.*;
public class GFG {
// Function to find the unique subsets
static List<List<Integer>> solve(List<Integer> v) {
// To store the resulting subsets
Set<List<Integer>> res = new HashSet<List<Integer>>();
List<Integer> subset;
int size = v.size();
// Finding 2^N
int N = 1 << size;
for (int i = 1; i < N; i++) {
int bit = i;
subset = new ArrayList<Integer>();
int pos = 0;
while (bit != 0) {
// If the bit is set, insert
// it into the subset
if ((bit & 1) != 0) {
subset.add(v.get(pos));
}
pos++;
bit >>= 1;
}
res.add(subset);
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
for (List<Integer> u : res)
result.add(u);
return result;
}
public static void main(String[] args) {
List<Integer> A = new ArrayList<Integer>();
A.add(1);
A.add(2);
A.add(2);
// Function call
List<List<Integer>> result = solve(A);
for (List<Integer> v : result) {
for (int i : v) {
System.out.print(i + " ");
}
System.out.println();
}
}
}
using System;
using System.Collections.Generic;
public class GFG {
// Function to find the unique subsets
static List<List<int>> Solve(List<int> v)
{
// To store the resulting subsets
HashSet<List<int>> res = new HashSet<List<int>>(new ListComparer<int>());
List<int> subset;
int size = v.Count;
// Finding 2^N
int N = 1 << size;
for (int i = 1; i < N; i++) {
int bit = i;
subset = new List<int>();
int pos = 0;
while (bit != 0) {
// If the bit is set, insert
// it into the subset
if ((bit & 1) != 0) {
subset.Add(v[pos]);
}
pos++;
bit >>= 1;
}
res.Add(subset);
}
List<List<int>> result = new List<List<int>>();
foreach (List<int> u in res) {
result.Add(u);
}
return result;
}
public static void Main() {
List<int> A = new List<int>();
A.Add(1);
A.Add(2);
A.Add(2);
// Function call
List<List<int>> result = Solve(A);
foreach (List<int> v in result) {
foreach (int i in v) {
Console.Write(i + " ");
}
Console.WriteLine();
}
}
// Custom comparer for list of integers
class ListComparer<T> : IEqualityComparer<List<T>> {
public bool Equals(List<T> x, List<T> y) {
if (x.Count != y.Count) {
return false;
}
for (int i = 0; i < x.Count; i++) {
if (!x[i].Equals(y[i])) {
return false;
}
}
return true;
}
public int GetHashCode(List<T> obj) {
int hash = 17;
foreach (T item in obj) {
hash = hash * 31 + item.GetHashCode();
}
return hash;
}
}
}
// This code is contributed by akashish__
// JS code to implement the approach
// Function to find the unique subsets
function solve(v) {
// To store the resulting subsets
let res = new Set()
subset = [];
let size = v.length;
// Finding 2^N
let N = 1 << size;
for (let i = 1; i < N; i++) {
let bit = i;
subset = [];
let pos = 0;
while (bit) {
// If the bit is set inset
// it into the subset
if (bit & 1) {
subset.push(v[pos]);
}
pos++;
bit >>= 1;
}
res.add(subset);
}
let result = [];
const iter = [...res];
// to store only unique arrays
let hashMap = {}
iter.forEach(function (arr) {
hashMap[arr.join("|")] = arr;
});
let result_temp = Object.keys(hashMap).map(function (k) {
return hashMap[k]
})
for (let i = 0; i < result_temp.length; i++) {
let u = result_temp[i];
result.push(u);
}
return result;
}
// Driver code
let A = [1, 2, 2];
// Function call
let result = solve(A);
console.log(result);
// This code is contributed by akashish__
# Python code to implement the approach
# Function to find the unique subsets
def solve(v):
# To store the resulting subsets
res = set()
subset = []
size = len(v)
# Finding 2^N
N = 1 << size
for i in range(1,N):
bit = i
subset = []
pos = 0
while bit:
# If the bit is set inset
# it into the subset
if bit & 1:
subset.append(v[pos])
pos += 1
bit >>= 1
res.add(tuple(subset))
result = []
iter = [x for x in res]
# to store only unique arrays
hashMap = {}
for arr in iter:
hashMap[str(arr)] = arr
result_temp = [v for _, v in hashMap.items()]
for i in range(len(result_temp)):
u = result_temp[i]
result.append(u)
return result
# Driver code
A = [1, 2, 2]
# Function call
result = solve(A)
print(result)
# This code is contributed by akashish__
Output
1 1 2 1 2 2 2 2 2
Time Complexity: O(N2 * 2N)
Auxiliary Space: O(2N)
Contact Us