Subsets

Subsets (Power Set) Problem

Problem Description

Given an integer array nums of unique elements, the task is to return all possible subsets (the power set). The solution set must not contain duplicate subsets, and the subsets can be returned in any order.

Naive Approach: Brute Force (Iterative)

The most straightforward approach is to generate all possible combinations of elements from the input array. We can iterate through all possible lengths of subsets, from 0 to the length of the input array, and generate all combinations for each length.

Algorithm:

1. Initialize an empty list result to store all subsets.
2. Iterate from i = 0 to n (inclusive), where n is the length of nums.
3. For each i, generate all combinations of length i from nums.
4. Add each generated combination to the result list.
5. Return the result list.

Code (Python):

from itertools import combinations

def subsets_brute_force(nums):
    result = []
    n = len(nums)
    for i in range(n + 1):
        for combo in combinations(nums, i):
            result.append(list(combo))
    return result

Time Complexity: O(n * 2^n), where n is the number of elements in nums. This is because we are generating all possible subsets (2^n) and copying each subset, which takes O(n) time.

Space Complexity: O(n * 2^n), to store all the subsets in the result list.

Optimal Approach: Backtracking

A more efficient approach is to use backtracking. We can build each subset by either including or excluding each element from the input array. This approach avoids generating unnecessary combinations and directly constructs the subsets.

Algorithm:

1. Initialize an empty list result to store all subsets.
2. Define a recursive function backtrack(index, current_subset):
   • Add the current_subset to the result list.
   • Iterate from i = index to the end of nums:
     • Include nums[i] in the current_subset.
     • Recursively call backtrack(i + 1, current_subset).
     • Exclude nums[i] from the current_subset (backtrack).
3. Call backtrack(0, []) to start the process with an empty subset.
4. Return the result list.

Code (Python):

def subsets(nums):
    result = []
    
    def backtrack(index, current_subset):
        result.append(current_subset[:])  # Add a copy of the current subset
        
        for i in range(index, len(nums)):
            current_subset.append(nums[i])
            backtrack(i + 1, current_subset)
            current_subset.pop()  # Backtrack: remove the last element
            
    backtrack(0, [])
    return result

Time Complexity: O(n * 2^n), where n is the number of elements in nums. We generate 2^n subsets, and copying each subset takes O(n) time.

Space Complexity: O(n), in the worst case, the depth of the recursion can go up to n. Additionally O(n * 2^n) space for storing all of the subsets.

Edge Cases

• Empty Input: If the input array nums is empty, the only subset is the empty set. The algorithm should correctly return [[]]. This case is implicitly handled by the backtracking algorithm since the initial subset will be empty.
• Single Element Input: If the input array nums contains only one element, the subsets are [] and [element]. The algorithm should correctly return [[], [element]]. This is handled correctly.
• Duplicate Elements: The problem statement specifies that the input array contains unique elements. If there were duplicate elements, the algorithm would still work, but the result would contain duplicate subsets. To avoid this, the input array should be preprocessed to remove duplicates, or additional logic should be added to the backtracking function to skip duplicate elements.

Summary

The backtracking approach provides an efficient way to generate all subsets of a given array. It has a time complexity of O(n * 2^n) and effectively handles edge cases such as empty or single-element inputs.