1.Subsets and Subset II

Given a set of distinct integers, nums, return all possible subsets (the power set).

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Solution: (Recursion)

class Solution
{
public:
    void computeSubsets(vector<int> v, vector<vector<int>> &res, int start, vector<int> &nums, int n)
    {

        if (start == n)
        {
            res.push_back(v);
            return;
        }

        computeSubsets(v, res, start + 1, nums, n);
        v.push_back(nums[start]);
        computeSubsets(v, res, start + 1, nums, n);
        return;
    }

    vector<vector<int>> subsets(vector<int> &nums)
    {
        vector<int> v;
        vector<vector<int>> res;
        int n = nums.size();

        computeSubsets(v, res, 0, nums, n);

        return res;
    }
};

Time complexity: O(N×2^N ) Space complexity: O(N×2^ N )

Solution: (Backtracking)

class Solution
{
public:
    void computeSubsets(vector<int> &v, vector<vector<int>> &res, int start, vector<int> &nums)
    {
        res.push_back(v);

        for (int i = start; i < nums.size(); i++)
        {
            v.push_back(nums[i]);
            computeSubsets(v, res, i + 1, nums);
            v.pop_back();
        }
        return;
    }

    vector<vector<int>> subsets(vector<int> &nums)
    {
        vector<int> v;
        vector<vector<int>> res;

        computeSubsets(v, res, 0, nums);

        return res;
    }
};

Time complexity: O(N×2^N ) Space complexity: O(N )

Subsets II: (No duplicates allowed)

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution: (Backtracking)

class Solution
{
public:
    void computeSubsets(vector<int> &v, vector<vector<int>> &res, int start, vector<int> &nums)
    {
        res.push_back(v);

        for (int i = start; i < nums.size(); i++)
        {
            if (i > start && nums[i] == nums[i - 1])
            {
                continue;
            }
            v.push_back(nums[i]);
            computeSubsets(v, res, i + 1, nums);
            v.pop_back();
        }
        return;
    }

    vector<vector<int>> subsetsWithDup(vector<int> &nums)
    {

        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> v;

        computeSubsets(v, res, 0, nums);

        return res;
    }
};

Time complexity: O(N * 2^N)