Subsequence Sum Problem
Logical Breakdown
- [ ] Subproblem Identification:
- [ ] Optimal Substructure:
- [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
- [ ] Optimization: (Matrix Exponentiation if 'A' is huge)
Mathematical Rigor
State Definition
Let \(dp[i]\) be the state for the \(i\)-th subproblem.
Recurrence Relation
Visualization
Complexity Analysis
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterative DP | \(O(N)\) | \(O(1)\) |
Code Reference
package com.dsa.recursion;
import java.util.*;
/ * Problem: Subsequence Sum Problem * Group: 07. Recursion */ / * ============================================================================================ * PROBLEM: Subsequence-Sum Problem (Subset Sum) * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * You are given an array of integers A of size N. * Determine if there exists any subsequence of A whose sum is exactly equal to B. * * Definition: * A subsequence is derived by deleting zero or more elements from the array without * changing the order of the remaining elements. * * --------------------- * 2. Logical Breakdown & Mathematical Formulation * --------------------- * Let A be the array [a_0, a_1, ..., a_{N-1}]. * Let F(index, currentSum) be a boolean function that returns true if it is possible * to reach the target B using a subset of elements from A[index...N-1], given the * sum so far is 'currentSum'. * * Decision Tree (Recursion): * At every index 'i', we have exactly two choices: * 1. INCLUDE A[i] in the subsequence: * New Sum = currentSum + A[i] * Recurse -> F(i + 1, currentSum + A[i]) * 2. EXCLUDE A[i] from the subsequence: * New Sum = currentSum * Recurse -> F(i + 1, currentSum) * * Recurrence Relation: * F(i, sum) = F(i + 1, sum + A[i]) OR F(i + 1, sum) * * Base Cases (Stopping Conditions): * 1. If sum == B : Return 1 (Target reached). * 2. If sum > B : Return 0 (Optimization: Since A[i] >= 1, sum can only increase. Prune branch). * 3. If i == N : Return 0 (Exhausted all elements without reaching B). * * --------------------- * 3. Constraints & Complexity Analysis * --------------------- * Constraints: * 1 <= N <= 20 * 1 <= A[i] <= 100,000 * 0 <= B <= 10^9 * * Time Complexity: * O(2^N) - In the worst case, we explore two branches for every element. * Since N <= 20, 2^20 approx 1,000,000 operations, which fits easily within 1 second. * * Space Complexity: * O(N) - The maximum depth of the recursion stack is N. * * Note on Alternatives: * - If N were larger (e.g., N=100) and B was small, we would use Dynamic Programming O(NB). * - Since B is large (10^9), DP is not feasible. The small N forces the recursive/bit-mask approach. * * --------------------- * 4. Input / Output Format * --------------------- * Input: * - Integer Array A. * - Integer B (Target Sum). * * Output: * - Return 1 if subsequence exists, else 0. * * --------------------- * 5. Examples * --------------------- * Input 1: A = [1, 20, 13, 4, 5], B = 18 * Path: Take 1 -> Take 13 -> Take 4. Sum = 1+13+4 = 18. * Output 1: 1 * * Input 2: A = [2, 2, 2, 2], B = 5 * Explanation: All sums will be even. 5 is odd. Impossible. * Output 2: 0 * * ============================================================================================ / public class SubsequenceSumProblem { public int solve(int[] a,int A) { // TODO: Implement solution return 0; } }