[Algorithm] Subsets

Subsets

Problem statement

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

Solution 1: DFS

We can DFS the given array and assemble the subsets. At each DFS depth, can pick any number. This solution is quite straight forward.

Code Implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; vector<int> path; dfs(result, nums, 0, path); return result; } void dfs(vector<vector<int>>& result, const vector<int>& nums, int pos, vector<int>& path) { result.push_back(path); for (int i=pos; i<nums.size(); i++) { path.push_back(nums[i]); dfs(result, nums, i+1, path); path.pop_back(); } } };

Solution 2: Bit manipulation.

Let's first consider this question, given N numbers how many different subsets it can possible make up, the answer is 2^N. So the if we have 32 numbers given the result won't even hold in the std::vector.

Why we are thinking about this? Now let's look at this, suppose 3 numbers are given [x, y, z], so what is the possible subsets:

1 2 3 4 5 6 7 8

[] -> [O, O, O] -> 000 [z] -> [O, O, z] -> 001 [y] -> [O, y, O] -> 010 [x] -> [x, O, O] -> 100 [x,y,z] -> [x, y, z] -> 111 [x,y] -> [x, y, O] -> 110 [y,z] -> [O, y, z] -> 011 [x,z] -> [x, O, z] -> 101

This means we can represent each subset as binary numbers, where bit 0 means skipping this number at this bit and bit 1 means number shows up at this bit.

So we just need to iterate from 0 -> 2^N-1 and set the numbers based on the binary representation of the current index.

(I used bitmap to implementation this simply because bitmap can allow me access bit with operator[]. You can certainly use int or long long)

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { assert(nums.size() <= 32); vector<vector<int> > result; int n = nums.size(); long long m = 1 << nums.size(); int i = 0; while (i < m) { std::bitset<32> mask(i); vector<int> path; result.push_back(path); for (int j=0; j<n; j++) { if (mask[j]) result.back().push_back(nums[j]); } i++; } return result; } };