Intermediate

Subset Problems

Subset problems ask you to enumerate all possible subsets of a collection, often with constraints like a target sum or no duplicates. The key insight is that at each element you make a binary decision: include it or skip it. This creates a binary decision tree with 2ⁿ leaves.

Problem 1: Subsets (LC 78)

Problem: Given an integer array of unique elements, return all possible subsets (the power set).

Example: nums = [1, 2, 3] → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Brute Force: Bit Manipulation

def subsets_brute(nums: list[int]) -> list[list[int]]:
    """Generate all subsets using bitmask enumeration.

    For n elements, iterate from 0 to 2^n - 1.
    Each bit position represents include/exclude.

    Time: O(2^n * n), Space: O(2^n * n)
    Works but not extensible to constraint-based variants.
    """
    n = len(nums)
    result = []

    for mask in range(1 << n):  # 0 to 2^n - 1
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)

    return result

Optimal: Backtracking (Collect at Every Node)

def subsets(nums: list[int]) -> list[list[int]]:
    """Generate all subsets via backtracking.

    Key difference from combinations: we add path to result
    at EVERY recursion level, not just when path reaches a
    specific length.

    Time: O(2^n * n) - 2^n subsets, O(n) to copy each
    Space: O(n) recursion depth
    """
    result = []

    def backtrack(start, path):
        result.append(path[:])  # collect at every node

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

# subsets([1,2,3]) -> [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Problem 2: Subsets II (LC 90)

Problem: Given an integer array that may contain duplicates, return all unique subsets.

Example: nums = [1, 2, 2] → [[], [1], [1,2], [1,2,2], [2], [2,2]]

Brute Force: Generate All, Deduplicate

def subsets_with_dup_brute(nums: list[int]) -> list[list[int]]:
    """Generate all subsets and remove duplicates using a set.

    Time: O(2^n * n * log(n)), Space: O(2^n * n)
    Wasteful: generates duplicates then filters them.
    """
    result_set = set()

    def backtrack(start, path):
        result_set.add(tuple(sorted(path)))
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return [list(s) for s in result_set]

Optimal: Sort + Skip Duplicates

def subsets_with_dup(nums: list[int]) -> list[list[int]]:
    """Unique subsets via backtracking with duplicate skipping.

    Sort the array first. Then at each recursion level, skip
    an element if it equals the previous element at the same level.
    This prevents generating the same subset via different orderings.

    Time: O(2^n * n), Space: O(n)
    """
    nums.sort()
    result = []

    def backtrack(start, path):
        result.append(path[:])

        for i in range(start, len(nums)):
            # Skip duplicate at the same recursion level
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

# subsets_with_dup([1,2,2]) -> [[], [1], [1,2], [1,2,2], [2], [2,2]]

Problem 3: Combination Sum II (LC 40)

Problem: Given a collection of candidate numbers (may contain duplicates) and a target, find all unique combinations where chosen numbers sum to target. Each number may be used only once.

Example: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8 → [[1,1,6], [1,2,5], [1,7], [2,6]]

Brute Force: Generate All Subsets, Filter by Sum

def combination_sum2_brute(candidates: list[int], target: int) -> list[list[int]]:
    """Generate all subsets and filter by target sum.

    Time: O(2^n * n), Space: O(2^n)
    Explores many branches that exceed the target.
    """
    result = set()

    def backtrack(start, path, total):
        if total == target:
            result.add(tuple(sorted(path)))
            return
        if total > target:
            return
        for i in range(start, len(candidates)):
            backtrack(i + 1, path + [candidates[i]], total + candidates[i])

    backtrack(0, [], 0)
    return [list(c) for c in result]

Optimal: Sort + Prune + Skip Duplicates

def combination_sum2(candidates: list[int], target: int) -> list[list[int]]:
    """Find unique combinations summing to target (no reuse).

    Three optimizations:
    1. Sort to enable pruning and duplicate detection
    2. Break early when candidate exceeds remaining sum
    3. Skip duplicates at the same recursion level

    Time: O(2^n) worst case, much faster with pruning
    Space: O(n) recursion depth
    """
    candidates.sort()
    result = []

    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return

        for i in range(start, len(candidates)):
            # Pruning: sorted array, so all future candidates too large
            if candidates[i] > remaining:
                break
            # Skip duplicates at same level
            if i > start and candidates[i] == candidates[i - 1]:
                continue

            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])
            path.pop()

    backtrack(0, [], target)
    return result

# combination_sum2([10,1,2,7,6,1,5], 8) -> [[1,1,6], [1,2,5], [1,7], [2,6]]

Problem 4: Target Sum / Subset Sum (LC 494 variant)

Problem: Given an array of non-negative integers and a target, determine if there exists a subset whose elements sum to the target.

Example: nums = [3, 34, 4, 12, 5, 2], target = 9 → True (subset [4, 5])

Brute Force: Check All 2ⁿ Subsets

def subset_sum_brute(nums: list[int], target: int) -> bool:
    """Check all subsets for target sum via recursion.

    At each element, include it or exclude it.

    Time: O(2^n), Space: O(n) recursion depth
    """
    def helper(idx, remaining):
        if remaining == 0:
            return True
        if idx >= len(nums) or remaining < 0:
            return False
        # Include nums[idx] OR exclude it
        return (helper(idx + 1, remaining - nums[idx]) or
                helper(idx + 1, remaining))

    return helper(0, target)

Optimal: Backtracking + Memoization (DP)

def subset_sum(nums: list[int], target: int) -> bool:
    """Subset sum with memoization (top-down DP).

    Cache (index, remaining) pairs to avoid recomputation.
    This converts O(2^n) to O(n * target) pseudo-polynomial.

    Time: O(n * target), Space: O(n * target)
    """
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def helper(idx, remaining):
        if remaining == 0:
            return True
        if idx >= len(nums) or remaining < 0:
            return False
        return (helper(idx + 1, remaining - nums[idx]) or
                helper(idx + 1, remaining))

    return helper(0, target)

# subset_sum([3, 34, 4, 12, 5, 2], 9) -> True

Problem 5: Partition to K Equal Sum Subsets (LC 698)

Problem: Given an array of integers and a number k, determine if the array can be divided into k non-empty subsets with equal sums.

Example: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 → True (subsets: [5], [1,4], [2,3], [2,3])

Brute Force: Try All Partitions

def can_partition_brute(nums: list[int], k: int) -> bool:
    """Try all possible assignments of elements to k buckets.

    Each element can go into any of k buckets.
    Time: O(k^n), Space: O(n)
    Extremely slow for large inputs.
    """
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    buckets = [0] * k

    def backtrack(idx):
        if idx == len(nums):
            return all(b == target for b in buckets)
        for j in range(k):
            if buckets[j] + nums[idx] <= target:
                buckets[j] += nums[idx]
                if backtrack(idx + 1):
                    return True
                buckets[j] -= nums[idx]
            # Optimization: if bucket is empty, no need to try other empty buckets
            if buckets[j] == 0:
                break
        return False

    return backtrack(0)

Optimal: Sort Descending + Backtracking with Pruning

def can_partition_k_subsets(nums: list[int], k: int) -> bool:
    """Partition into k equal-sum subsets with aggressive pruning.

    Key optimizations:
    1. Sort descending: large numbers fail fast, prune early
    2. Skip identical bucket values (symmetry breaking)
    3. If any single element exceeds target, return False immediately
    4. If bucket is empty after failure, stop trying other buckets

    Time: O(k^n) worst case, much faster with pruning
    Space: O(n) recursion depth
    """
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k

    nums.sort(reverse=True)  # large elements first for fast pruning

    if nums[0] > target:
        return False

    buckets = [0] * k

    def backtrack(idx):
        if idx == len(nums):
            return True  # all elements assigned

        seen = set()  # avoid trying identical bucket states
        for j in range(k):
            if buckets[j] + nums[idx] > target:
                continue
            if buckets[j] in seen:
                continue  # symmetry breaking
            seen.add(buckets[j])

            buckets[j] += nums[idx]
            if backtrack(idx + 1):
                return True
            buckets[j] -= nums[idx]

            # If this bucket is empty and we failed, no point trying others
            if buckets[j] == 0:
                break

        return False

    return backtrack(0)

# can_partition_k_subsets([4,3,2,3,5,2,1], 4) -> True

Complexity Summary

Problem	Brute Force	Optimal	Key Optimization
Subsets	O(2n × n)	O(2n × n)	Backtracking is already optimal
Subsets II	O(2n × n log n)	O(2n × n)	Sort + skip duplicates at same level
Combination Sum II	O(2n)	O(2n) with heavy pruning	Sort + break when > remaining
Subset Sum	O(2n)	O(n × target)	Memoization (top-down DP)
Partition K Subsets	O(kn)	O(kn) with pruning	Sort desc + symmetry breaking