78. Subsets
1. Description
Given an integer array nums, return all possible subsets (the power set).
The solution set must not contain duplicate subsets.
2. Example
Example 1
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2
Input: nums = [0]
Output: [[],[0]]
3. Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
4. Solutions
Bit Manipulation
n = i_nums.size()
Time complexity: O($2^nn$)
Space complexity: O($2^nn$)
class Solution
{
public:
// vector<vector<int>> subsets(vector<int>& nums)
vector<vector<int>> subsets(vector<int> &i_nums)
{
vector<int> subSet;
vector<vector<int>> result;
for(int i = 0; i < (1 << i_nums.size()); i++)
{
for(int j = 0; j < i_nums.size(); j++)
{
if(i & (1 << j))
subSet.push_back(i_nums[j]);
}
result.push_back(subSet);
subSet.clear();
}
return result;
}
};
Backtracking
n = i_nums.size()
Time complexity: O($2^nn$)
Space complexity: O($2^nn$)
class Solution
{
private:
vector<int> subSet;
vector<vector<int>> result;
void subsets(int currentPosition, vector<int> &i_nums)
{
if(currentPosition == i_nums.size())
{
result.push_back(subSet);
return ;
}
subSet.push_back(i_nums[currentPosition]);
subsets(currentPosition + 1, i_nums);
subSet.pop_back();
subsets(currentPosition + 1, i_nums);
}
public:
// vector<vector<int>> subsets(vector<int>& nums)
vector<vector<int>> subsets(vector<int> &i_nums)
{
subsets(0, i_nums);
return result;
}
};