Subsets (Backtracking)

import sys
from typing import List

class Solution:
    # Optimized: O(N * 2^N) Time, O(N * 2^N) Space - Backtracking/DFS
    def subsets_optimal(self, nums: List[int]) -> List[List[int]]:
        results = []
        
        def backtrack(index, current_subset):
            # Base Case: All elements checked, save the subset
            results.append(list(current_subset))
            
            for i in range(index, len(nums)):
                # 1. Choose (Include nums[i])
                current_subset.append(nums[i])
                
                # 2. Recurse
                backtrack(i + 1, current_subset)
                
                # 3. Backtrack (Exclude nums[i] for the next iteration at this depth)
                current_subset.pop()

        backtrack(0, [])
        return results

    # Alternative Optimal: O(N * 2^N) Time, O(N * 2^N) Space - Bit Manipulation
    def subsets_bit_manipulation(self, nums: List[int]) -> List[List[int]]:
        results = []
        N = len(nums)
        # Iterate through all 2^N masks
        for i in range(1 << N):
            subset = []
            for j in range(N):
                # Check if the j-th bit is set in the mask i
                if (i >> j) & 1:
                    subset.append(nums[j])
            results.append(subset)
        return results

import java.util.ArrayList;
import java.util.List;

class Solution {
    
    // Optimized: O(N * 2^N) Time, O(N * 2^N) Space - Backtracking/DFS
    public List<List<Integer>> subsets_optimal(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), results);
        return results;
    }

    private void backtrack(int[] nums, int start, List<Integer> current_subset, List<List<Integer>> results) {
        // Add the subset found at this depth
        results.add(new ArrayList<>(current_subset));

        for (int i = start; i < nums.length; i++) {
            // 1. Choose
            current_subset.add(nums[i]);
            
            // 2. Recurse
            backtrack(nums, i + 1, current_subset, results);
            
            // 3. Backtrack
            current_subset.remove(current_subset.size() - 1);
        }
    }
    
    // Alternative Optimal: O(N * 2^N) Time, O(N * 2^N) Space - Bit Manipulation
    public List<List<Integer>> subsets_bit_manipulation(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        int N = nums.length;
        int total_subsets = 1 << N; 

        for (int i = 0; i < total_subsets; i++) {
            List<Integer> subset = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                // Check if the j-th bit is set
                if (((i >> j) & 1) == 1) {
                    subset.add(nums[j]);
                }
            }
            results.add(subset);
        }
        return results;
    }
}

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

class Solution {
private:
    vector<vector<int>> results;

    // Helper for Optimal: Backtracking/DFS
    void backtrack(const vector<int>& nums, int index, vector<int>& current_subset) {
        // Base Case: Add the current subset to results
        results.push_back(current_subset);

        for (int i = index; i < nums.size(); ++i) {
            // 1. Choose
            current_subset.push_back(nums[i]);
            
            // 2. Recurse (Note: recurse with i + 1)
            backtrack(nums, i + 1, current_subset);
            
            // 3. Backtrack
            current_subset.pop_back();
        }
    }

public:
    // Optimized: O(N * 2^N) Time, O(N * 2^N) Space - Backtracking
    vector<vector<int>> subsets_optimal(const vector<int>& nums) {
        results.clear();
        vector<int> current_subset;
        backtrack(nums, 0, current_subset);
        return results;
    }

    // Alternative Optimal: O(N * 2^N) Time, O(N * 2^N) Space - Bit Manipulation
    vector<vector<int>> subsets_bit_manipulation(const vector<int>& nums) {
        vector<vector<int>> bit_results;
        int N = nums.size();
        int total_subsets = 1 << N; // 2^N

        for (int i = 0; i < total_subsets; ++i) {
            vector<int> subset;
            for (int j = 0; j < N; ++j) {
                // Check if the j-th bit is set in the mask i
                if ((i >> j) & 1) {
                    subset.push_back(nums[j]);
                }
            }
            bit_results.push_back(subset);
        }
        return bit_results;
    }
};