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.

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Different Approaches

1️⃣ Bit Manipulation

Intuition:

The power set of a given array is the set of all possible subsets of the array, including the empty set and the set itself. Each element can either be included in a subset or not, resulting in 2n (where n is the number of elements) possible subsets.

Approach:

1. Each subset can be represented by a binary number of length n (where n is the size of the array). If the binary number is 101, it means the subset includes the elements at positions 1 and 3 of the array.
2. Store the size of array, the count of subarrays in variables. Declare a list of lists to return the required answer.
3. Loop through all possible values from 0 to count-1. Initialize an empty list for the current subset.
4. For each value, use its binary representation to decide which elements are included in the current subset. Loop through each bit of the current value. If the bit is set, add the corresponding element from the array in the subset.
5. Add all the subsets generated to the list of list which can be returned as our answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function call to get the
    Power set of given array */
    vector<vector<int>> powerSet(vector<int>& nums) {
        
        // Variable to store size of array
        int n = nums.size();
        
        // To store the answer
        vector<vector<int>> ans;
        
        /* Variable to store the 
        count of total susbsets */
        int count = (1 << n);
        
        // Traverse for every value
        for(int val = 0; val < count; val++) {
            
            // To store the current subset
            vector<int> subset;
            
            // Traverse on n bits
            for(int i=0; i < n; i++) {
                if(val & (1 << i)) {
                    subset.push_back(nums[i]);
                }
            }
            
            /* Add the current subset 
            to final answer */
            ans.push_back(subset);
        }
        
        // Return stored answer
        return ans;
    }
};

int main() {
    vector<int> nums = {1, 2, 3};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the
    Power set of given array */
    vector<vector<int>> ans = sol.powerSet(nums);
    
    sort(ans.begin(), ans.end());
    
    // Output
    cout << "The power set for the given array is: " << endl;
    
    for(int i=0; i < ans.size(); i++) {
        for(int j=0; j < ans[i].size(); j++) {
            cout << ans[i][j] << " ";        
        }
        cout << endl;
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(2^n * n) (where n is the size of the array) –
  • The outer loop runs for count numbers of times, and count is 2^n resulting in O(2^n).
  • The inner for loop runs to check n bits, resulting in O(n).
• Space Complexity: O(2^n*n) – Space required to store the power set (approximately).