Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Subsets II

Moderate

0/80

Average time to solve is 45m

Contributed by

71 upvotes

Asked in companies

Problem statement

Ninja is observing an array of ‘N’ numbers and wants to make as many unique subsets as possible. Can you help the Ninja to find all the unique subsets?

Note: Two subsets are called same if they have same set of elements.For example {3,4,1} and {1,4,3} are not unique subsets.

You are given an array ‘ARR’ having N elements. Your task is to print all unique subsets.

For Example

For the given if ARR = [1,1,3],the answer will be [ ],[1],[1,1],[1,3],[3],[1,1,3].

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of elements.
The second line of each test case contains ‘ARR’ array.

Output Format:

For each test case, print all the subsets in each line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.
Return the output in sorted format as shown in the sample output.

Constraints:

1 <= T <= 10
1 <= N <= 20.
1 <= ARR[i] <=100

Time limit: 1 sec

Sample Input 1:

Sample Output 1:

Explanation of sample input 1:

For the first test case,
The unique subsets will be  [ ],[1],[1,1],[1,3],[3],[1,1,3]. 

For the second test case:
The unique subsets will be  [ ],[1,3],[1,3,3],[1,3,3,3],[3],[3,3],[3,3,3].

Sample Input 2:

Sample Output 2:

Hint 1

Hint 2

Hint 3

Try to remove the duplicate subsets.

Approaches (3)

Approach 1

Approach 2

Approach 3

Iterative Method

If there are N elements in the array, then a total of 2^N subsets are possible as each element have two choices either to include it or not.

How many of them are duplicates?

We can treat the duplicate elements as special elements. For example, if we have duplicate elements (5, 5), instead of treating them as two elements that are duplicate, we can treat it as one special element 5, but this element has more than two choices: you can either NOT put it into the subset, or put ONE 5 into the subset, or put TWO 5s into the subset.

So if A[i] has a frequency of ‘F’, then there are F+1 choices.

Therefore, we are given an array (a1, a2, a3, ..., an) with each of them appearing (k1, k2, k3, ..., kn) times, the number of subsets is (k1+1)(k2+1)...(kn+1).

In this approach,we will first sort the array and find the frequency of each element. If the frequency of element ‘X’ is ‘F’, then we will append no Xs ,1 Xs, 2Xs … F Xs to the end of the already made subsets. We will do the following for all unique elements.

Algorithm:

Declare a variable array of arrays ‘SUBSETS’ to store the subsets.
Insert an empty array to ‘SUBSETS’.
Sort the given array ‘ARR’.
Set i as 0.
While i is less than ‘N’, do the following:
- Set ‘C’ as 0 to store the frequency of the element.
- While i+c < N and ARR[i] is equal to ARR[i+c]:
  - Set ‘C’ as ‘C’+1.
- Set M as the length of ‘SUBSETS’.
- For j in range 0 to M-1:
  - Set ‘CUR’ as SUBSETS[j].
  - For k in range 0 to ‘C’:
    - Append ARR[i] to CUR.
    - Insert ‘CUR’ to ‘SUBSETS’.
- Set i as i+ count.
Return ‘SUBSETS’ list containing all the unique subsets.

Time Complexity

O(2^N ), where ‘N’ is the number of elements in ‘ARR’.

In this approach, we are finding all the unique subsets of the given array. If all the elements of the array are distinct, then the total number of subsets will be 2^N. Hence, the overall time complexity is O(2^N)

Space Complexity

O(2^N ), where ‘N’ is the number of elements in ‘ARR’.

In this approach, we are storing all the unique subsets in a list and at the worst case, the number of the unique subsets can be 2^N. Hence, the overall space complexity is O(2^N).

(75% EXP penalty)

(100% EXP penalty)

Subsets II

Jenil Panchal

Interview problems

Easy python solution

from itertools import combinations

def uniqueSubsets(n :int,arr :List[int]) -> List[List[int]]:

arr.sort()

subsets = []

for r in range(n+1):

subsets += list(set(combinations(arr, r)))

return subsets

7 views

0 replies

0 upvotes

Vaibhav kumar choudhary

Interview problems

subsets II java

import java.util.*;

public class Solution {

public static void findSubsets(int ind, int[] nums, List<Integer> ds, List<List<Integer>> ansList) {

ansList.add(new ArrayList<>(ds));

for(int i = ind;i<nums.length;i++) {

if(i!=ind && nums[i] == nums[i-1]) continue;

ds.add(nums[i]);

findSubsets(i+1, nums, ds, ansList);

ds.remove(ds.size() - 1);

}

public static ArrayList<ArrayList<Integer>> uniqueSubsets(int n, int arr[]) {

Arrays.sort(arr);

List<List<Integer>> ansList = new ArrayList<>();

findSubsets(0, arr, new ArrayList<>(), ansList);

ArrayList<ArrayList<Integer>> uniqueSubsets = new ArrayList<>();

for (List<Integer> subset : ansList) {

uniqueSubsets.add(new ArrayList<>(subset));

}

return uniqueSubsets;

}

public static void main(String[] args) {

int[] nums = {1, 2, 2};

ArrayList<ArrayList<Integer>> result = uniqueSubsets(nums.length, nums);

for (ArrayList<Integer> subset : result) {

System.out.println(subset);

}

105 views

0 replies

0 upvotes

Aakrit Bhandari

Interview problems

C++ || Solution Using Recursion || Just one change to the Basic Method

#include<bits/stdc++.h>

void subset(int i, vector<vector<int>>& get, vector<int>& ii, vector<int>& arr) {

if (i == arr.size()) {

get.push_back(ii);

return;

}

ii.push_back(arr[i]);

subset(i + 1, get, ii, arr);

ii.pop_back();

while(i+1<arr.size()&&arr[i]==arr[i+1])i++;

subset(i + 1, get, ii, arr);

}

vector<vector<int>> uniqueSubsets(int n,vector<int>& arr) {

sort(arr.begin(), arr.end());

vector<vector<int>> get;

vector<int> ii;

subset(0, get, ii, arr);

sort(get.begin(),get.end());

return get;

}

356 views

0 replies

0 upvotes

Abhishek Sachdeva

Interview problems

let me know where i am making mistake || i guess it's right ||c++

#include <bits/stdc++.h>

vector<vector<int>> uniqueSubsets(int n, vector<int> &arr)

{

// Write your code here.

vector<vector<int>>ans;

for(int i=0; i<pow(2,n); ++i)

{

vector<int>subset;

for(int j=0; j<n; ++j)

{

if((1<<j)&i)

{

subset.push_back(arr[j]);

}

ans.push_back(subset);

}

sort(ans.begin(),ans.end());

ans.erase(unique(ans.begin(),ans.end()),ans.end());

return ans;

}

71 views

0 replies

0 upvotes

Shreshth Jha

Interview problems

Java solution

public class Solution {

public static ArrayList<ArrayList<Integer>> uniqueSubsets(int n, int arr[]) {

// Write your code here..

Arrays.sort(arr); // Sort the array to handle duplicates

ArrayList<ArrayList<Integer>> result = new ArrayList<>();

ArrayList<Integer> currentSubset = new ArrayList<>();

powerset(arr, 0, currentSubset, result);

return result;

}

public static void powerset(int[] nums, int start, ArrayList<Integer> currentSubset, ArrayList<ArrayList<Integer>> result) {

result.add(new ArrayList<>(currentSubset));

for (int i = start; i < nums.length; i++) {

// Skip duplicates

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

continue;

}

currentSubset.add(nums[i]);

powerset(nums, i + 1, currentSubset, result);

currentSubset.remove(currentSubset.size() - 1);

}

107 views

0 replies

0 upvotes

Ahmed Elnoor

Interview problems

Unique SubsetII

public class Solution {

public static ArrayList<ArrayList<Integer>> uniqueSubsets(int n, int arr[]) {

// Write your code here..

// sort the array

Arrays.sort(arr);

// create subset

ArrayList<ArrayList<Integer>> subset = new ArrayList<>();

// find the subset by doing recrusion

findSubset(0, arr, new ArrayList<>(), subset);

// return the subset

return subset;

}

private static void findSubset(int ind, int[] nums, List<Integer> ds,ArrayList<ArrayList<Integer>> subset){

subset.add(new ArrayList<>(ds));

// iterate over the length

for(int idx =ind; idx < nums.length; idx++){

if(idx != ind && nums[idx]==nums[idx-1]) continue;

ds.add(nums[idx]);

findSubset(idx+1, nums,ds,subset);

ds.remove(ds.size() - 1);

}

83 views

0 replies

1 upvote

Ajay Jakhar

Interview problems

C++ SOLUTION || Using Recursion || Easy Approach

#include <bits/stdc++.h>

void helper(vector<int>&nums , vector<int>&subset , vector<vector<int>>&ans ,int i){

if(i == nums.size()){

ans.push_back(subset);

return;

}

subset.push_back(nums[i]);

helper(nums,subset,ans,i+1);

subset.pop_back();

while(i+1 < nums.size() && nums[i]==nums[i+1]) i++;

helper(nums,subset,ans,i+1);

}

vector<vector<int>> uniqueSubsets(int n, vector<int> &nums)

{

sort(nums.begin(),nums.end());

vector<vector<int>>ans;

vector<int>subset;

helper(nums,subset,ans,0);

sort(ans.begin(),ans.end());

return ans;

}

216 views

0 replies

0 upvotes

Interview problems

Java Unique Subsets II Recursion easy solution.

import java.util.* ;
import java.io.*;
public class Solution {
public static void f(int ind, ArrayList<ArrayList<Integer>> ans,List<Integer> ds,
int arr[],int n){

ans.add(new ArrayList<>(ds));
for(int i = ind; i < n;i++){
if(i != ind && arr[i] == arr[i-1])continue;
ds.add(arr[i]);
f(i+1,ans,ds,arr,n);
ds.remove(ds.size()-1);
}

}
public static ArrayList<ArrayList<Integer>> uniqueSubsets(int n, int arr[]) {
// Write your code here..
Arrays.sort(arr);
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
f(0,ans,new ArrayList<>(),arr,n);
return ans;
}

}

datastructures

126 views

0 replies

0 upvotes

Kamal Thakur

Interview problems

python using set solution


def find_unique_subsets(arr):
    arr.sort()
    def backtrack(start, subset):
        unique_subsets.add(tuple(subset))
        for i in range(start, len(arr)):
            subset.append(arr[i])
            backtrack(i + 1, subset)
            subset.pop()

    unique_subsets = set()
    backtrack(0, [])
    
    
    return [list(subset) for subset in unique_subsets]

67 views

0 replies

0 upvotes

Kamal Thakur

Interview problems

python solution by Kamal

python easy and understandable approach

100% Working

  
def uniqueSubsets(n :int,arr :List[int]) -> List[List[int]]:

    # Write your code here.
    arr.sort()
    def backtrack(start,subset):
        result.append(subset.copy())
        for i in range(start,len(arr)):
            if i!=start and arr[i]==arr[i-1]:
                continue
            subset.append(arr[i])
            backtrack(i+1,subset)
            subset.pop()
    result=[]
    backtrack(0,[])
    return result

python

55 views

0 replies

0 upvotes

Console