Subsets medium

Problem Statement

Given an integer array nums, 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]]

Steps

The problem of finding all subsets of a set is equivalent to generating all possible combinations of including or excluding each element in the set. We can solve this using a recursive approach or an iterative approach (using bit manipulation). Here, we'll focus on a recursive backtracking approach.

1. Base Case: If the input array is empty, return a list containing only an empty list (the empty subset).

2. Recursive Step: For each element in the input array:

   • Recursively generate all subsets of the remaining array (excluding the current element).
   • For each of those subsets, create a new subset by adding the current element to it.
   • Add both the subsets (with and without the current element) to the overall result.

Explanation

The recursive approach systematically explores all possibilities. Consider nums = [1,2,3].

• Starting with an empty subset [].
• We consider 1: Recursively find subsets of [2,3]. This will return [[], [2], [3], [2,3]]. We then add 1 to each of these, resulting in [[1], [1,2], [1,3], [1,2,3]]. We combine these with the subsets of [2,3] to get [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]].

This process continues until all elements are processed.

Code (C++)

#include <vector>

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

private:
    void generateSubsets(const std::vector<int>& nums, int index, std::vector<int>& currentSubset, std::vector<std::vector<int>>& result) {
        if (index == nums.size()) {
            result.push_back(currentSubset);
            return;
        }

        // Exclude the current element
        generateSubsets(nums, index + 1, currentSubset, result);

        // Include the current element
        currentSubset.push_back(nums[index]);
        generateSubsets(nums, index + 1, currentSubset, result);
        currentSubset.pop_back(); // Backtrack: remove the element for the next iteration
    }
};

Complexity

• Time Complexity: O(2ⁿ * n), where n is the number of elements in the input array. This is because there are 2ⁿ possible subsets, and adding each element to a subset takes O(n) in the worst case.

• Space Complexity: O(2ⁿ * n) to store all the subsets. The recursion depth is O(n) in the worst case.