78. Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

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]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

Approach 01:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        solve(nums, 0, {}, result);
        return result;
    }

private:
    void solve(const vector<int>& nums, int s, vector<int>&& path, vector<vector<int>>& result) {
        result.push_back(path);

        for (int i = s; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            solve(nums, i + 1, move(path), result);
            path.pop_back();
        }
    }
};

from typing import *

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []

        def solve(s: int, path: List[int]) -> None:
            result.append(path)

            for i in range(s, len(nums)):
                solve(i + 1, path + [nums[i]])

        solve(0, [])
        return result

Time Complexity

• Number of subsets: The total number of subsets of a set with n elements is \( 2^n \). This is because each element can either be included in a subset or not, leading to \( 2^n \) combinations.
• Subset generation: For each subset, the algorithm performs operations proportional to the size of the subset, which in the worst case is n.
• Therefore, the time complexity can be expressed as: Time Complexity = \( O(n \cdot 2^n) \)
• This accounts for generating \( 2^n \) subsets and processing each subset, which involves copying and manipulating up to n elements in the worst case.

Space Complexity

• Recursion stack: The depth of the recursion is n because the recursion goes through each element once. Therefore, the space used by the recursion stack is O(n).
• Result storage: The algorithm stores all subsets in the result vector. Since there are \( 2^n \) subsets and each subset can have up to n elements, the space required to store all subsets is: Space Complexity for storing subsets = \( O(n \cdot 2^n) \)
• Intermediate storage: The space required for the intermediate path vector at any given time is O(n) in the worst case when the recursion goes to the deepest level.
• Combining these, the overall space complexity is dominated by the space required to store the subsets: Total Space Complexity = \( O(n \cdot 2^n) \)