Subsets - II Editorial

Practice Problem Link: Subsets - II

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an array of integers A, return all possible subsets. The array might contain duplicates. Note: The list should not contain any duplicate subsets.

Approach

The Approach to solve this problem is basically brute force to generate all the subsets. We can observe that for every element, we have a choice to either take it in the current subset or not. We can form a mask of length n, where if the ith element of the mask is set, we take that element into our current subset. After forming the subset, we check in our current list of subsets if this subset is present or not, if yes, then it is discarded, else added into our list. This technique is known as Bitmasking. We can also solve it recursively using a backtracking-based approach.

Analysis

• Time Complexity: O(n * 2ⁿ * logn)
• Space Complexity: O(n * 2ⁿ)

Implementation

Recursive Approach 

C++

void getSubsets(vector<int> &A, int start, vector<int> currSubset, vector<vector<int>> &allSubsets) {
	if (start == A.size()) {
		allSubsets.push_back(currSubset);
		return;
	}
	int indx = 1;
	while (start + indx < A.size() && A[start] == A[start + indx]) {
		indx++;
	}
	getSubsets(A, start + indx, currSubset, allSubsets);
	currSubset.push_back(A[start]);
	getSubsets(A, start + 1, currSubset, allSubsets);
}
vector<vector<int>> subsets(vector<int> &A) {
	sort(A.begin(),A.end());
	vector<vector<int>> allSubsets;
	vector<int> currSubset;
    getSubsets(A, 0, currSubset, allSubsets);
	return allSubsets;
}

Java

class Solution {	
	void getSubsets(int[] A, int start, List<Integer> currSubset, List<List<Integer>> allSubsets) {
		if (start == A.length) {
			allSubsets.add(new ArrayList(currSubset));
			return;
		}
		int indx = 1;
		while (start + indx < A.length && A[start] == A[start + indx]) {
			indx++;
		}
		getSubsets(A, start + indx, currSubset, allSubsets);
		currSubset.add(A[start]);
		getSubsets(A, start + 1, currSubset, allSubsets);
		currSubset.remove(currSubset.size() - 1);
	}
	List<List<Integer>> subsets(int[] A) {
		Arrays.sort(A);
		List<List<Integer>> allSubsets = new ArrayList<>();
		List<Integer> currSubset = new ArrayList<>();
		getSubsets(A, 0, currSubset, allSubsets);
		return allSubsets;
	}
}

Iterative Implementation

C++

vector<vector<int>> bitmask(vector<int> &a, int n) {
    vector<vector<int>> allSubsets;
    for(int mask = 0; mask < (1LL << n); mask++) {
		vector<int> subsets;
        for(int i = 0; i < n; i++) {
            if((1LL << i) & mask) {
                subsets.push_back(a[i]);
            }
        }
		sort(subsets.begin(), subsets.end());
		if(find(allSubsets.begin(), allSubsets.end(), subsets) == allSubsets.end()) {
        	allSubsets.push_back(subsets); 
		}
    }
    return allSubsets;
}
vector<vector<int>> subsets(vector<int> &A) {
    vector<vector<int>> result = bitmask(A, A.size());
	return result;
}

Java

class Solution {
	List<List<Integer>> subsets(int[] A) {
		Arrays.sort(A);
		int n = A.length;
		List<List<Integer>> list = new ArrayList<>();
		for(int mask = 0; mask < Math.pow(2,n); mask++){
			List<Integer> subsets = new ArrayList<>();
			for(int i = 0; i < n; i++) {
				if(((1 << i) & mask) != 0) {
					subsets.add(A[i]);
				}
			}
			if(checkIfValid(list, subsets)) {
				list.add(subsets);
			}
		}
		return list;
	}
	boolean checkIfValid(List<List<Integer>> list, List<Integer> subsets){
		int flag = 0;
		for(List<Integer> i: list){
			int counter = 0;
			if(i.size() != subsets.size()) {
				continue;
			} else {
				flag = 1;
				for(int j = 0 ; j < subsets.size(); j++) {
					if(i.get(j) == subsets.get(j)) {
						counter++;
					}
				}
				if(counter == subsets.size()) {
					return false;
				}
			}
		}
		return true;
	}
}