# 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;
    }
};