Subsets — Bitmask Enumeration
Sanjeev SharmaAdvertisement
Problem
Given an integer array of unique elements, return all possible subsets.
Approach — Bitmask
For n elements, there are 2^n subsets. Each mask from 0 to 2^n-1 represents one subset.
Time: O(2^n * n) | Space: O(2^n * n)
Solutions
Python — Bitmask
class Solution:
def subsets(self, nums: list[int]) -> list[list[int]]:
n=len(nums); result=[]
for mask in range(1<<n):
subset=[nums[i] for i in range(n) if mask&(1<<i)]
result.append(subset)
return result
Python — Backtracking
class Solution:
def subsets(self, nums: list[int]) -> list[list[int]]:
result=[];
def bt(i,curr):
result.append(list(curr))
for j in range(i,len(nums)):
curr.append(nums[j]); bt(j+1,curr); curr.pop()
bt(0,[]); return result
C++
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums){
int n=nums.size(); vector<vector<int>> res;
for(int mask=0;mask<(1<<n);mask++){
vector<int> sub;
for(int i=0;i<n;i++) if(mask&(1<<i)) sub.push_back(nums[i]);
res.push_back(sub);
}
return res;
}
};
Complexity
- Time: O(2^n * n) | Space: O(2^n * n)
Advertisement
