1. Complexity Hierarchy: Combinatorial Explosion to Pseudo-Polynomial DP

Understanding the computational boundaries of the Subset Sum problem is essential for selecting the appropriate engineering approach:

• Exponential Combinatorial Branching (Brute Force): For each element in an array of size n, a subset generator has two choices: include the element or exclude it. This binary decision tree generates 2^n possible subsets. For n = 50, evaluating 2^50 ≈ 1.125 × 10^15 states would take months of compute time on modern silicon.
• Top-Down Recursion with Memoization: By defining a recursive function solve(index, remainingSum), we can cache overlapping subproblems in a 2D lookup table memo[n][sum]. While this avoids recalculating identical states, it incurs significant call-stack overhead and requires O(n × sum) memory.
• Bottom-Up 2D Tabulation: Constructing a boolean table dp[n+1][sum+1] where dp[i][j] indicates whether a subset of the first i elements can sum to j. The recurrence transition is defined as:

  dp[i][j] = dp[i-1][j] || (j >= arr[i-1] ? dp[i-1][j - arr[i-1]] : false)

• The 1D Rolling Array Space Optimization: Notice that row i depends exclusively on the previous row i-1. By iterating backwards from sum down to arr[i], we can compress the entire 2D table into a single 1D boolean array of size sum + 1, eliminating O(n) row allocations.

2. The Backward Traversal Invariant (0-1 Knapsack Guard)

Why must the 1D rolling array be traversed in reverse order (from sum down to val)?

If you iterate forward from val up to sum, updating dp[j] = dp[j] || dp[j - val] allows a newly computed true state at index j to immediately propagate into j + val, j + 2*val, and so forth within the same iteration. This effectively converts the problem into the Unbounded Knapsack problem, where an element can be selected an infinite number of times!

By traversing backwards, dp[j - val] always represents state from the previous item iteration. Each number is evaluated exactly once, preserving the strict 0-1 Knapsack property.

3. Bitset Optimization: 64x Speedup via CPU Word Parallelism

In high-performance C++, when the target sum is bounded (e.g., sum ≤ 100,000), we can leverage bit-level parallelism via std::bitset. A single bitwise left shift (<<) moves all boolean flags across 64-bit machine words simultaneously:

// std::bitset enables O((n * sum) / 64) execution speed!
std::bitset<100001> dp;
dp[0] = 1; // Base case: sum of 0 is always achievable

for (int num : arr) {
    dp |= (dp << num); // Shifts all reachable sums by num in a single CPU cycle!
}

return dp[sum];

Because the CPU performs bitwise operations on 64-bit integer registers, the inner loop executes 64 times faster than a standard scalar boolean loop, delivering near-instantaneous subset sum evaluation.

4. Production C++20 Implementation (1D DP & Bitset)

#include <vector>
#include <bitset>

class Solution {
public:
    // Standard 1D Space-Optimized Dynamic Programming
    bool isSubsetSum(const std::vector<int>& arr, int sum) {
        if (sum == 0) return true;
        if (arr.empty()) return false;

        // 1D rolling boolean table
        std::vector<bool> dp(sum + 1, false);
        dp[0] = true; // Base case

        for (int num : arr) {
            // Traverse backwards to enforce 0-1 Knapsack invariant
            for (int j = sum; j >= num; --j) {
                if (dp[j - num]) {
                    dp[j] = true;
                }
            }
            // Early exit optimization
            if (dp[sum]) return true;
        }

        return dp[sum];
    }

    // High-Performance Bitset Solution for Bounded Sums
    bool isSubsetSumBitset(const std::vector<int>& arr, int sum) {
        if (sum < 0) return false;
        if (sum == 0) return true;

        constexpr size_t MAX_SUM = 50001;
        if (static_cast<size_t>(sum) >= MAX_SUM) {
            return isSubsetSum(arr, sum); // Fallback to 1D DP for huge sums
        }

        std::bitset<MAX_SUM> dp;
        dp[0] = 1;

        for (int num : arr) {
            dp |= (dp << num);
            if (dp[sum]) return true;
        }

        return dp[sum];
    }
};

5. Production TypeScript Implementation

Below is the equivalent 1D space-optimized dynamic programming solution in TypeScript, utilizing a typed Uint8Array to maximize CPU cache locality and avoid JavaScript object allocation overhead:

/**
 * Subset Sum Problem in TypeScript
 * Time Complexity: O(n * sum)
 * Auxiliary Space Complexity: O(sum) using typed Uint8Array
 */
export function isSubsetSum(arr: number[], sum: number): boolean {
  if (sum === 0) return true;
  if (arr.length === 0 || sum < 0) return false;

  // Use Uint8Array as high-density boolean buffer
  const dp = new Uint8Array(sum + 1);
  dp[0] = 1; // Base case: sum 0 is achievable with empty subset

  for (let i = 0; i < arr.length; i++) {
    const val = arr[i];
    // Traverse backwards to prevent element re-use
    for (let j = sum; j >= val; j--) {
      if (dp[j - val] === 1) {
        dp[j] = 1;
      }
    }
    // Early exit
    if (dp[sum] === 1) return true;
  }

  return dp[sum] === 1;
}

6. Conclusion & Algorithmic Takeaways

The Subset Sum Problem illustrates the progression of algorithm design: recognizing NP-completeness, designing pseudo-polynomial dynamic programming models, compacting spatial footprints into 1D rolling buffers, and exploiting microarchitectural bitwise parallelism. In production systems, mastering these data-structure nuances allows engineers to transform theoretical NP-hard hurdles into lightning-fast, production-grade solutions.