Subset Sum and Combination Problems

Finding the Right Combinations: Backtracking for Sum Problems

Imagine you have a collection of coins and need to find which combination adds up to exactly $10. Or perhaps you need to select items from a store that total a specific budget. These are classic examples of subset sum and combination sum problems that backtracking solves elegantly.

These problems showcase how backtracking can systematically explore combinatorial spaces while applying constraints to prune invalid paths.

Subset Sum Problem

Problem Statement

Given a set of positive integers and a target sum, find if there exists a subset that sums to the target.

Input: Array of integers, target sum
Output: True if subset exists, False otherwise

Backtracking Solution

def subset_sum(nums, target):
    def backtrack(index, current_sum):
        # Base cases
        if current_sum == target:
            return True
        if current_sum > target or index == len(nums):
            return False

        # Try including current element
        if backtrack(index + 1, current_sum + nums[index]):
            return True

        # Try excluding current element
        return backtrack(index + 1, current_sum)

    return backtrack(0, 0)

Finding All Subsets

def find_all_subsets(nums, target):
    result = []

    def backtrack(index, current_sum, current_subset):
        if current_sum == target:
            result.append(current_subset[:])
            return

        if current_sum > target or index == len(nums):
            return

        # Include current element
        current_subset.append(nums[index])
        backtrack(index + 1, current_sum + nums[index], current_subset)
        current_subset.pop()

        # Exclude current element
        backtrack(index + 1, current_sum, current_subset)

    backtrack(0, 0, [])
    return result

Combination Sum Problem

Problem Statement

Given an array of distinct integers and a target, find all unique combinations that sum to target. Each number may be used multiple times.

Backtracking Solution

def combination_sum(candidates, target):
    result = []

    def backtrack(index, current_sum, current_combo):
        if current_sum == target:
            result.append(current_combo[:])
            return

        if current_sum > target:
            return

        for i in range(index, len(candidates)):
            # Include candidates[i] (can use multiple times)
            current_combo.append(candidates[i])
            backtrack(i, current_sum + candidates[i], current_combo)
            current_combo.pop()

    backtrack(0, 0, [])
    return result

Combination Sum II (No Duplicates)

Each number may only be used once.

def combination_sum2(candidates, target):
    candidates.sort()  # Sort to handle duplicates
    result = []

    def backtrack(index, current_sum, current_combo):
        if current_sum == target:
            result.append(current_combo[:])
            return

        for i in range(index, len(candidates)):
            if i > index and candidates[i] == candidates[i-1]:
                continue  # Skip duplicates

            if current_sum + candidates[i] > target:
                break  # No need to continue (sorted)

            current_combo.append(candidates[i])
            backtrack(i + 1, current_sum + candidates[i], current_combo)
            current_combo.pop()

    backtrack(0, 0, [])
    return result

Key Differences

Aspect	Subset Sum	Combination Sum	Combination Sum II
Element Usage	Once each	Multiple times	Once each
Order Matters	No	No	No
Duplicates	Allowed in input	Allowed in input	Handled in output
Backtracking Choice	Include/Exclude	Include (same or next)	Include (next only)

Optimization Techniques

Early Termination

Stop exploring when sum exceeds target:

def backtrack(index, current_sum):
    if current_sum == target:
        return True
    if current_sum > target or index == len(nums):
        return False
    # Continue exploring...

Sorting for Pruning

Sort candidates to enable early termination:

candidates.sort()
# In loop:
if current_sum + candidates[i] > target:
    break  # No larger numbers needed

Memoization (Advanced)

Cache results for subproblems (though less common in backtracking).

Time Complexity Analysis

Subset Sum

Worst Case: O(2^n) - all subsets
With Pruning: Much better in practice
Space: O(n) for recursion stack

Combination Sum

Worst Case: Exponential
With Pruning: Depends on constraints
Space: O(target/min_candidate) for recursion

Real-World Applications

Cryptography

Knapsack Cryptosystem: Based on subset sum hardness
Subset Sum Problems: Used in some encryption schemes

Resource Allocation

Budget Optimization: Select items within budget constraints
Project Selection: Choose projects that fit resource limits

Manufacturing

Cutting Stock Problem: Minimize waste when cutting materials
Bin Packing: Pack items efficiently

Finance

Portfolio Optimization: Select investments within budget
Change Making: Find optimal coin combinations

Common Patterns

Decision Problems

Return true/false if solution exists:

def has_subset_sum(nums, target):
    def backtrack(index, current_sum):
        if current_sum == target:
            return True
        if current_sum > target or index == len(nums):
            return False

        # Include
        if backtrack(index + 1, current_sum + nums[index]):
            return True

        # Exclude
        return backtrack(index + 1, current_sum)

    return backtrack(0, 0)

Enumeration Problems

Find all valid solutions:

def find_all_combinations(nums, target):
    result = []

    def backtrack(index, current_sum, combo):
        if current_sum == target:
            result.append(combo[:])
            return

        for i in range(index, len(nums)):
            if current_sum + nums[i] <= target:
                combo.append(nums[i])
                backtrack(i + 1, current_sum + nums[i], combo)
                combo.pop()

    backtrack(0, 0, [])
    return result

Handling Edge Cases

Empty Arrays

if not nums:
    return target == 0  # Empty subset sums to 0

Negative Numbers

More complex - can lead to infinite loops if not handled carefully.

Large Targets

May need additional pruning based on remaining sum.

Performance Tips

Sort Input: Enables better pruning
Use Early Termination: Stop when sum exceeds target
Avoid Duplicates: Skip identical elements when appropriate
Choose Right Variant: Subset vs Combination vs Combination II

Key Takeaways

Subset sum finds subsets that sum to target (each element once)
Combination sum finds combinations that sum to target (elements reusable)
Backtracking systematically explores all possibilities
Pruning dramatically improves performance

Subset sum and combination problems demonstrate backtracking's versatility in solving combinatorial problems with sum constraints, teaching us how to explore solution spaces efficiently while respecting mathematical constraints.