Power Set

Problem Statement

Given an array of integers nums of unique elements. Return all possible subsets (power set) of the array.

Do not include the duplicates in the answer.

Power set = A set of all subsets. The total number of subsets in the power set is 2^n, because for each element in the set, there are two possibilities: either it is included in a subset or it is not.

LeetCode Links:

• Subset 1 (LeetCode 78) (Unique Elements)
• Subset 2 (LeetCode 90) (With Duplicates)

✏️Constraints:

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

Examples

Example 1:

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

Explanation: There are a total of 2^n possible subsets.
             2^n = 2^3 = 8 subsets.

Example 2:

Input: nums = [1, 2]
Output: [
         [],
         [1],
         [2],
         [1, 2]
        ]
        
Explanation: There are a total of 2^n = 2^2 = 4 subsets

Example 3:

Input: nums = [0]
Output: [
         [],
         [0]
        ]

🚀 Different Approaches

1️⃣ Recursion

🧠 Intuition:

Recursion is a natural way to solve the power set problem because we can think about building subsets by making decisions at each step. Here's how to think about it:

1. Base Case: If there are no elements left to consider, the only subset we can create is the empty set.
2. Recursive Case: For each element, we have two choices:
   • Include the current element in the subset.
   • Exclude the current element from the subset.

By recursively making these choices for each element, we generate all possible subsets.

Recursive Approach:

1. Start from the first element and recursively generate subsets by including or excluding the current element.
2. Move to the next element and repeat the process.
3. Collect all subsets and return them.

Dry Run:

nums = {1, 2, 3}

1. Start with an empty subset current = {}.
2. At each element, make a decision to include or exclude it:
   • Exclude 1, then exclude 2, then exclude 3 → {}
   • Exclude 1, then exclude 2, then include 3 → {3}
   • Exclude 1, then include 2, then exclude 3 → {2}
   • Exclude 1, then include 2, then include 3 → {2, 3}
   • Include 1, then exclude 2, then exclude 3 → {1}
   • Include 1, then exclude 2, then include 3 → {1, 3}
   • Include 1, then include 2, then exclude 3 → {1, 2}
   • Include 1, then include 2, then include 3 → {1, 2, 3}

Output:

{ }
{ 3 }
{ 2 }
{ 2, 3 }
{ 1 }
{ 1, 3 }
{ 1, 2 }
{ 1, 2, 3 }

🧑‍💻 Code: Subset1 (Unique Elements)

// C++ code to generate all subsets using recursion

#include <iostream>
#include <vector>

void generateSubsets(std::vector<int>& nums, int index, std::vector<int>& current, std::vector<std::vector<int>>& powerSet) {
    // Base case: if we have considered all elements
    if (index == nums.size()) {
        powerSet.push_back(current);
        return;
    }
    
     // Include the current element in the subset and move to the next
    current.push_back(nums[index]);
    generateSubsets(nums, index + 1, current, powerSet);
    // Backtrack to remove the current element from the subset
    current.pop_back();
    
    // Exclude the current element and move to the next
    generateSubsets(nums, index + 1, current, powerSet);

}

std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
    std::vector<std::vector<int>> powerSet;
    std::vector<int> current;
    generateSubsets(nums, 0, current, powerSet);
    return powerSet;
}

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<std::vector<int>> result = subsets(nums);

    // Print the power set
    for (const auto& subset : result) {
        std::cout << "{ ";
        for (int num : subset) {
            std::cout << num << " ";
        }
        std::cout << "}\n";
    }

    return 0;
}

💡 Handling Duplicates: Subsets II

🧠 Intuition:

This will handle the duplicates by:

• Sorting the nums array, for bringing the duplicate elements together, which makes it easier to skip them.
• When deciding to exclude an element, we skip all subsequent duplicates of the current element to avoid generating duplicate subsets.

🧑‍💻 Code : Handling Duplicates (Subset 2)

class Solution {
public:
    void solve(vector<vector<int>>& result, vector<int>& nums, vector<int>& output, int index) {
        // Base Case: If we've processed all elements
        if (index == nums.size()) {
            result.push_back(output);  // Add the current subset to the result
            return;
        }

        // Include the current element
        output.push_back(nums[index]);
        solve(result, nums, output, index + 1);  // Move to the next element
        output.pop_back();  // Backtrack to try excluding the current element

        // Exclude the current element and skip duplicates
        int nextIndex = index + 1;
        while (nextIndex < nums.size() && nums[nextIndex] == nums[index]) {
            nextIndex++;  // Skip duplicate elements
        }
        solve(result, nums, output, nextIndex);
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;  // To store all unique subsets
        vector<int> output;  // Temporary vector to build subsets

        // Sort the nums array to bring duplicates together
        sort(nums.begin(), nums.end());

        // Start the recursive backtracking
        solve(result, nums, output, 0);
        return result;
    }
};

Complexity Analysis:

• Time Complexity:O(2^n * n)
  • Number of subsets: There are 2^n subsets in the power set because each element can either be included or excluded, resulting in 2 possibilities per element.
  • Time to Process Each Subset: For each subset, we might spend O(n) time to create or store it, since copying or printing the subset takes linear time in terms of the number of element.
• Space Complexity:O(2^n * n)
  • Output Space: We need to store all 2^n subsets, and each subset could contain up to n elements.
  • Recursive Call Stack: In the recursive solution, the call stack can go up to O(n) in depth.

2️⃣ Bitmasking

🧠 Intuition:

Each element has 2 choices: include or exclude.

That means there are 2^n subsets.

Each subset can be represented by a bitmask of length n, where:

• 1 at position i -> include nums[i]
• 0 at position i -> exclude nums[i]

🔁 Example:

nums = [1, 2, 3]

Binary: 000 → []
Binary: 001 → [3]
Binary: 010 → [2]
Binary: 011 → [2, 3]
Binary: 100 → [1]
...

🧑‍💻 Code: Bitmasking

vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();               // Step 1: Get the size of the input array
    int total = 1 << n;                // Step 2: Total number of subsets = 2^n (using bit shifting)
    vector<vector<int>> res;          // Step 3: This will store all the subsets

    // Step 4: Loop through all possible bitmasks from 0 to 2^n - 1
    for (int mask = 0; mask < total; ++mask) {
        vector<int> subset;           // Step 5: Start with an empty subset

        // Step 6: For each bit position, check if it is set in the current mask
        for (int j = 0; j < n; ++j) {
            // Step 7: If the j-th bit is set, include nums[j] in the subset
            if (mask & (1 << j)) {
                subset.push_back(nums[j]);
            }
        }

        // Step 8: Add the constructed subset to the result
        res.push_back(subset);
    }

    // Step 9: Return the final list of all subsets
    return res;
}

Complexity Analysis:

• Time Complexity:O((2 ^ n) * n))
  • As it loop through 2^n masks and check n bit each
• Space Complexity: O(1)

🧠 Summary Table

Final Thoughts

• Both recursion and bitmasking are effective for generating subsets.
• Choose recursion for intuitive understanding and bitmasking for performance in interviews.
• Always remember to sort the array when dealing with duplicates.