Subsequence Sum Existence

# Question

Given an array $nums$ of $n$ integers and a target $k$, return true if there exists a subsequence such that the sum of its elements equals $k$. Otherwise, return false.

# Solution 1: Top-Down (The Decision Tree)

Pattern: Backtracking with Memoization.

• Intuition: We simulate every possible subsequence. If we hit the same (index, k) twice, we return the cached result.
• Code Logic: solve(idx + 1, k) || solve(idx + 1, k - nums[idx])

# Solution 2: Bottom-Up (The Building Blocks)

Pattern: Tabulation.

• Intuition: We fill a 2D grid. Each cell represents a "State" of reachability.
• Decision: dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]].

# Solution 3: Space Optimized (The Collapsed Row)

Pattern: 1D DP Array.

• Intuition: Since we only ever look at the "previous" row, we use one array and update it in place.
• The Catch: You must iterate backwards through the sums to prevent a single number from being "re-used" to reach a larger sum in the same iteration.

# Pattern

Dynamic Programming (0/1 Knapsack Variation) This problem is a classic "Subset Sum" problem where each element can either be included or excluded to reach a target value.

# How to Identify

• Subsequence/Subset requirement: Looking for a combination of elements.
• Fixed Target: The goal is a specific sum $k$.
• Binary Choice: At each element, the only decision is: "Do I pick this or not?"

# Description

Step-by-step explanation:

1. State Definition: We use a boolean array dp of size $k+1$, where dp[i] is true if a sum $i$ can be formed using a subset of elements seen so far.
2. Base Case: dp[0] = true because a sum of 0 is always possible using an empty subsequence.
3. Iterative Processing: For each number num in nums:
   • We iterate backwards through the dp array from $k$ down to num.
   • Backwards Loop: This is critical. By going from $k \to num$, we ensure that each element is only used once. If we went forward, we would effectively solve the "Unbounded" version (reusing elements).
4. Update Rule: dp[i] = dp[i] || dp[i - num]. If the sum i - num was possible, then adding the current num makes sum i possible.
5. Early Exit: If dp[k] becomes true at any point, we return immediately.

# The Core DP Transition: dp[i] = dp[i - num]

# The Logical Meaning

This line represents the State Transition Equation. It connects a problem you've already solved to a slightly larger problem you're trying to solve now.

# The Components

1. i: The target sum we are currently considering.
2. num: The current element from the array we are "trying out."
3. i - num: The "remainder." The sum we would need to have already formed to make i possible.
4. dp[i - num]: A boolean check. "Is the remainder actually possible?"

# Why No "Else"?

You'll notice there is no else { dp[i] = false; }. This is because if dp[i] was already True (found by a different combination of numbers earlier), we don't want to overwrite it with False. Once a sum is reachable, it stays reachable.

# Concepts to Think About

• Space Optimization: We only look at i - num, which is always a smaller index than i. This is why we can get away with a 1D array.
• The "Take" Decision: This if statement represents the "Take" branch of your recursion. The "Don't Take" branch is handled automatically because if we don't enter the if, dp[i] simply keeps its previous value.

# The Intuition

Think of the dp array as a reachability map. Initially, only position 0 is reachable. When you encounter a number (e.g., 5), you look at all currently reachable spots and "jump" 5 units forward from them to mark new reachable spots. Repeating this for all numbers eventually tells you if position $k$ is reachable.

# Complexity

# Time Complexity

We iterate through $N$ elements, and for each, we scan up to $K$ values in the dp array. Total operations $\approx N \times K$.

# Space Complexity

We only maintain a single 1D array of size $K+1$. No recursion stack is used.

# Code

class Solution {
    public boolean checkSubsequenceSum(int[] nums, int k) {
        // dp[i] represents if sum 'i' is achievable
        boolean[] dp = new boolean[k + 1];
 
        // Base case: sum 0 is always possible
        dp[0] = true;
 
        for (int num : nums) {
            // Optimization: if num > k, it cannot contribute to sum k (assuming positive nums)
            if (num > k) continue;
 
            // Update dp table backwards to prevent using same element multiple times
            for (int i = k; i >= num; i--) {
                if (dp[i - num]) {
                    dp[i] = true;
                }
            }
 
            // Early exit
            if (dp[k]) return true;
        }
 
        return dp[k];
    }
}

# Caveats

• Negative Values: If the array contains negative numbers, the target $k$ is no longer a strict upper bound for the DP array. You would need to shift the range or use a HashSet to store possible sums.
• Large $K$: If $K$ is very large (e.g., $10^9$), but $N$ is small ($\le 40$), DP will fail due to memory. Use Meet-in-the-middle instead.

# Concepts to Think About

• 0/1 Knapsack: This is exactly the same logic as the knapsack problem, where "weight" and "value" are the same.
• Bit Manipulation (Ultimate Optimization): In Java, you can use java.util.BitSet. The update becomes bitset.or(bitset.shiftLeft(num)). This uses bitwise parallelism to speed up the $O(K)$ loop by a factor of 64.
• Reconstructing the Solution: To find which numbers form the sum, you would need the $O(N \cdot K)$ 2D matrix to backtrack.
• Space Optimization: Why backward? If you go forward: $dp[5]$ becomes true from $dp[0]$, then $dp[10]$ becomes true from $dp[5]$ in the same iteration, effectively using the number '5' twice.

# Why Bottom-Up Works (The Snapshot Rule)

# The Logic

Bottom-Up DP is just a way of saying: "If I have a set of possible sums, and I get a new number $x$, my new set of possible sums is (Old Sums) $\cup$ (Old Sums + $x$)."

# Why the Backward Loop is Mandatory

• 0/1 Knapsack (Use each once): We must update the array using only the "Old" information. By moving backwards ($k \to num$), we ensure that when we check dp[i-num], it hasn't been touched by the current number yet. It is a "clean" value from the previous iteration.
• Unbounded Knapsack (Use many times): If the problem allowed you to use the same number infinitely, you would move forwards.

# Decision Choice

• Recursive (Top-Down): Starts at the goal and asks "What do I need to get here?"
• Iterative (Bottom-Up): Starts at 0 and asks "What can I reach from here?"

# Logical Follow-up

Question: What if $K$ is $10^9$ and $N$ is 30? Solution: Use Meet-in-the-middle. Split the array into two halves of size 15. Generate all possible $2^{15}$ sums for each half (Total $\approx 32,768$ sums each). Sort one set and for each sum $s$ in the other set, binary search for $k-s$. Total time: $O(2^{n/2} \cdot n)$.

Question: What if you can use each number an infinite number of times? Solution: This is the Coin Change variation. Change the inner loop to run forward from num to $k$. This allows the current number to be added repeatedly to previously formed sums in the same pass.