# 78. Subsets
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
# Solution
Approach 1: Based on the size of each subset.
Approach 2: Based on whether each number is selected or not.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
// Based on the size of each subset.
class Solution {
private:
void subsets(vector<int>& subset, vector<vector<int>>& allSubsets, vector<int>& nums, int head, int level) {
if (level == 0)
{
allSubsets.push_back(subset);
return;
}
for (int i = head; i < nums.size(); ++i)
{
subset.push_back(nums[i]);
subsets(subset, allSubsets, nums, i + 1, level - 1);
subset.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> allSubsets;
vector<int> subset;
for (int i = 0; i <= nums.size(); ++i)
{
subsets(subset, allSubsets, nums, 0, i);
}
return allSubsets;
}
};
Approach 2:
// Based on whether each number is selected or not.
class Solution {
private:
void subsets(vector<int>& subset, vector<vector<int>>& allSubsets, vector<int>& nums, int level) {
if (level == nums.size())
{
allSubsets.push_back(subset);
return;
}
// Not select this number.
subsets(subset, allSubsets, nums, level + 1);
// Select this number.
subset.push_back(nums[level]);
subsets(subset, allSubsets, nums, level + 1);
subset.pop_back();
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> allSubsets;
vector<int> subset;
subsets(subset, allSubsets, nums, 0);
return allSubsets;
}
};