Searching & SortingProblem 33 of 36

Subset Sums

Brute Force
Time: O(2^n)
Space: O(2^n)
Optimal
Time: O(2^(n/2) * log(2^(n/2)))
Space: O(2^(n/2))

Problem Statement

Given a set of N integers, find the number of subsets whose sum is equal to a given target sum S.

Constraints:

  • 1 ≤ N ≤ 40
  • -10^9 ≤ arr[i] ≤ 10^9
  • -10^18 ≤ S ≤ 10^18

Example:

  • Input: arr = [1, 2, 3, 4, 5], S = 10
  • Output: 3
  • Explanation: Subsets with sum 10: 5, 5, 4

Example 2:

  • Input: arr = [1, 1, 1, 1], S = 2
  • Output: 6
  • Explanation: All pairs sum to 2

Approach 1: Brute Force (Generate All Subsets)

Intuition

Generate all 2^n subsets, calculate sum of each, and count those equal to target.

Algorithm

  1. Use recursion/iteration to generate all subsets
  2. For each subset, calculate sum
  3. Count subsets with sum equal to S
java
public class Solution {
    private int count = 0;
    
    private void countSubsetsRecursive(int[] arr, int idx, long currentSum, long target) {
        if (idx == arr.length) {
            if (currentSum == target) count++;
            return;
        }
        
        // Include
        countSubsetsRecursive(arr, idx + 1, currentSum + arr[idx], target);
        
        // Exclude
        countSubsetsRecursive(arr, idx + 1, currentSum, target);
    }
    
    public int countSubsets(int[] arr, long S) {
        count = 0;
        countSubsetsRecursive(arr, 0, 0, S);
        return count;
    }
}

Complexity Analysis

  • Time Complexity: O(2^n) - Generate all subsets
  • Space Complexity: O(n) for recursion stack, O(2^n) if storing all subsets

Approach 2: Meet in the Middle (Optimal for N ≤ 40)

Intuition

Split the array into two halves. Generate all subset sums for each half (2^(n/2) each), then use two-pointer or binary search to find pairs that sum to target.

Key Observations:

  1. For N = 40, 2^40 is too large (~10^12)
  2. But 2^20 is manageable (~10^6)
  3. Split array: generate sums of both halves
  4. For each sum in first half, find complement in second half

Algorithm

  1. Split array into two halves
  2. Generate all subset sums for each half
  3. Sort second half sums
  4. For each sum in first half, binary search for (target - sum) in second half
  5. Count total matches
java
import java.util.*;

public class SubsetSum {
    private List<Long> generateSubsetSums(int[] arr, int start, int end) {
        int n = end - start;
        List<Long> sums = new ArrayList<>();
        
        for (int mask = 0; mask < (1 << n); mask++) {
            long sum = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum += arr[start + i];
                }
            }
            sums.add(sum);
        }
        
        return sums;
    }
    
    private int lowerBound(List<Long> list, long target) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid) < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
    
    private int upperBound(List<Long> list, long target) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid) <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
    
    public long countSubsets(int[] arr, long S) {
        int n = arr.length;
        int mid = n / 2;
        
        List<Long> leftSums = generateSubsetSums(arr, 0, mid);
        List<Long> rightSums = generateSubsetSums(arr, mid, n);
        
        Collections.sort(rightSums);
        
        long count = 0;
        
        for (long leftSum : leftSums) {
            long target = S - leftSum;
            
            int lower = lowerBound(rightSums, target);
            int upper = upperBound(rightSums, target);
            
            count += (upper - lower);
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        SubsetSum ss = new SubsetSum();
        int[] arr = {1, 2, 3, 4, 5};
        System.out.println(ss.countSubsets(arr, 10));  // Output: 3
    }
}

Dry Run Example

arr = [1, 2, 3, 4, 5], S = 10 Step 1: Split array Left half: [1, 2] Right half: [3, 4, 5] Step 2: Generate subset sums Left sums: [0, 1, 2, 3] (from subsets: {}, {1}, {2}, {1,2}) Right sums: [0, 3, 4, 7, 5, 8, 9, 12] (from subsets: {}, {3}, {4}, {3,4}, {5}, {3,5}, {4,5}, {3,4,5}) Step 3: Sort right sums Right sums sorted: [0, 3, 4, 5, 7, 8, 9, 12] Step 4: For each left sum, find complement Left sum = 0: target = 10 Binary search for 10 in [0, 3, 4, 5, 7, 8, 9, 12] Not found, count += 0 Left sum = 1: target = 9 Binary search for 9 in [0, 3, 4, 5, 7, 8, 9, 12] Found 1 occurrence (index 6) count += 1 Subset: {1} + {4,5} = {1,4,5} ✓ Left sum = 2: target = 8 Binary search for 8 in [0, 3, 4, 5, 7, 8, 9, 12] Found 1 occurrence (index 5) count += 1 Subset: {2} + {3,5} = {2,3,5} ✓ Left sum = 3: target = 7 Binary search for 7 in [0, 3, 4, 5, 7, 8, 9, 12] Found 1 occurrence (index 4) count += 1 Subset: {1,2} + {3,4} = {1,2,3,4} ✓ Total count: 3

Complexity Analysis

  • Time Complexity: O(2^(n/2) × log(2^(n/2))) = O(2^(n/2) × n)
    • Generate subsets: O(2^(n/2))
    • Sort: O(2^(n/2) × log(2^(n/2)))
    • Binary search for each left sum: O(2^(n/2) × log(2^(n/2)))
  • Space Complexity: O(2^(n/2)) - Storing subset sums

Variant: Two Pointer Approach

Instead of binary search, use two pointers after sorting both halves:

Key Takeaways

  1. Meet in the Middle: Reduces O(2^n) to O(2^(n/2)) by splitting the problem
  2. Subset Sum Generation: Use bitmask to generate all 2^n subsets
  3. Binary Search for Complement: For each left sum, find target-sum in right
  4. Handle Duplicates: Use lower_bound and upper_bound to count multiple occurrences
  5. Large N Constraint: Meet in the Middle works for N ≤ 40 (where 2^20 ≈ 10^6)
  6. Space Trade-off: We trade space (storing 2^(n/2) sums) for time
  7. Applications: Cryptography, combinatorics, competitive programming
Previous
DoubleHelix SPOJ
Next
Find the inversion count