leetcode-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 numbers in nums are unique.

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

        def backtrack(start, current_subset):
            # Add current subset to result
            result.append(current_subset[:])  # Make a copy!

            # Try adding each remaining element
            for i in range(start, len(nums)):
                current_subset.append(nums[i])  # Include nums[i]
                backtrack(i + 1, current_subset)  # Recurse
                current_subset.pop()  # Backtrack (exclude nums[i])

        backtrack(0, [])
        return result

    # Approach 2: Iterative
    def subsets2(self, nums: List[int]) -> List[List[int]]:
        result = [[]]  # Start with empty subset

        for num in nums:
            # For each existing subset, create new subset by adding num
            new_subsets = [subset + [num] for subset in result]
            result.extend(new_subsets)

        return result

    # Approach 3: Bit Manipulation
    def subsets3(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []

        # There are 2^n subsets
        for mask in range(1 << n):
            subset = []
            for i in range(n):
                # Check if i-th bit is set
                if mask & (1 << i):
                    subset.append(nums[i])
            result.append(subset)

        return result

# Time Complexity: O(2^n * n) - 2^n subsets, O(n) to create each
# Space Complexity: O(n) - recursion depth for backtracking
#
# Key Pattern: Backtracking for generating combinations
# start index prevents duplicates by ensuring we only consider
# elements after the current position