Subsets Editorial

Practice Problem Link: Subsets

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

Problem Statement

Given an array of distinct integers A, return all possible subsets. 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. This technique is known as Bitmasking. We can also use brute force backtracking to solve the problem recursively.

Analysis

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

Implementation

Recursive Version

C++

void getSubsets(vector<int> &A, int start, vector<int> &currSubset, vector<vector<int>> &allSubsets) {
	if (start == A.size()) {
		allSubsets.push_back(currSubset);
		return;
	}
	getSubsets(A, start + 1, currSubset, allSubsets);
	currSubset.push_back(A[start]);
	getSubsets(A, start + 1, currSubset, allSubsets);
	currSubset.pop_back();
}
vector<vector<int>> subsets(vector<int> &A) {
	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;
		}
		getSubsets(A, start + 1, currSubset, allSubsets);
		currSubset.add(A[start]);
		getSubsets(A, start + 1, currSubset, allSubsets);
		currSubset.remove(currSubset.size() - 1);
	}
	List<List<Integer>> subsets(int[] 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]);
            }
        }
        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) {
		List<List<Integer>> answer = new ArrayList<>();
		int n = A.length;
		for(int mask = 0; mask <= Math.pow(2,n) - 1; mask++) {
			List<Integer> subsets = new ArrayList<>();
			for(int i = 0; i < n; i++) {
				if((1<<i & mask) != 0) {
					subsets.add(A[i]);
				}
			}
			answer.add(subsets);
		}
		return answer;
	}
}