Problem statement
Return true if some subsequence sums to k; otherwise return false. Values may be skipped, but their order cannot change. The original takeUforward prompt has 1–20 positive values (1–100) and a positive target k≤2000.
For [1, 2, 3, 4, 5], k=8, [1, 2, 5] is one witness. We need not find or count the others. For [4, 3, 9, 2], k=10, the result is false.
Because k>0, any successful subsequence is non-empty. Our helper treats zero remaining as success; if extending the contract to a non-empty subsequence with k=0, add a chosen flag instead of accepting the empty choice.
Constraints & requirements
- CONTRACT
- Return a boolean, not a count. Every array index may be selected at most once.
Examples 3 test cases
Example 1 Case 1
- Input
nums=[1,2]; k=2- Output
true
The witness requires skipping the first value.
Example 2 Case 2
- Input
nums=[4,3,9,2]; k=10- Output
false
Both choices must fail before false.
Example 3 Case 3
- Input
nums=[2]; k=2- Output
true
The last value can close the gap.
Hints Optional
01Find the smaller problem
You need one witness, not every witness.
02Define the state
Carry the next index and the gap remaining. Taking subtracts a value; skipping keeps the gap.
03Connect the recurrence
Return true when the gap is zero; try skip only after take fails. Positive-target DP uses OR, not addition.
How to think before coding
Name one state as the undecided index and the remaining target. Its answer is a boolean: can this suffix finish the target? Taking and skipping are alternatives, so combine them with OR and stop after success. For nonnegative bounded sums, repeated (index,remaining) states suggest DP. Preserve the nonempty-selection rule when a zero target is possible.
Baseline and recursive approach
Your local practice/CheckSubsequenceSum.java calculates both take and notTake before returning their OR. That is correct enumeration of the choices, but the second call has already run, so the final OR cannot save that work. The published version returns immediately after a successful take branch. Your isSelected flag enforces a nonempty witness for target zero; the original positive-target task needs no such distinction. This article’s explicitly labelled empty-allowed extension must not be confused with that nonempty variant.
The bit-mask baseline tests every non-empty selection and stops at the first success. It takes O(n·2ⁿ) worst-case time. A recursive baseline avoids recomputing each sum from scratch:
public static boolean hasSubsequence(int[] nums, int k) {
return existsFrom(nums, 0, k); // remaining is the amount the undecided suffix must supply.
}
private static boolean existsFrom(int[] nums, int index, int remaining) {
if (remaining == 0) return true; // A witness has already been found; further choices aren't needed.
if (index == nums.length) return false; // No undecided values remain to close a nonzero gap.
if (existsFrom(nums, index + 1, remaining - nums[index])) return true; // Take; stop on success.
return existsFrom(nums, index + 1, remaining); // Try skipping only if taking failed.
}The first condition is deliberate: remaining==0 proves success even when index==n. Reversing the checks would reject a valid selection that uses the last element.
Why not keep exploring after true? Existence needs only one witness. Further successes do not change true. Counting must instead explore and add both branches.
Why no remaining<0 pruning? It is safe for strictly positive input, but not for a generalized array with negatives. For [3, -1], target 2, taking 3 makes remaining −1, then taking −1 reaches zero. This teaching recursion deliberately omits that pruning.
Intuition: ask the suffix to supply the missing amount
Start with remaining=k. If we take value x, the suffix only needs remaining−x. If we skip x, it still needs remaining.
This is equivalent to tracking a running sum, but expresses a useful question: can the undecided suffix fill this gap?
Optimized solution: boolean subset-sum DP
public static boolean hasSubsequenceDp(int[] nums, int k) {
boolean[] reachable = new boolean[k + 1]; // reachable[s] means processed indexes can form s.
reachable[0] = true; // Choosing nothing forms zero; the actual target k is positive.
for (int value : nums) { // Consider one new position at a time.
for (int sum = k; sum >= value; sum--) { // Descend so each position is used at most once.
reachable[sum] |= reachable[sum - value]; // Keep old witnesses or extend one with value.
}
}
return reachable[k]; // Existence needs a boolean, not a frequency.
}reachable[sum] stores a fact, not a count: “some choice of processed positions can reach this sum.” Each new value can either be skipped (keep the old fact) or taken (read reachable[sum−value]).
The descending loop prevents reusing the same position within its own update. This method relies on nonnegative values and k≥0; it is not a general negative-number DP.
Recursion tree and short-circuiting
For [1, 2], k=2:
exists(0,2) ├─ take 1 → exists(1,1) │ ├─ take 2 → exists(2,-1) returns false │ └─ skip 2 → exists(2,1) returns false │ returns false └─ skip 1 → exists(1,2) ├─ take 2 → exists(2,0) returns true └─ skip 2 → NOT CALLED (a witness already exists) returns true root returns true
A skipped branch is not a failed branch. It has no returned value, because it was never executed. In a paper trace, cross out a short-circuited sibling instead of drawing a false-returning child.
Dry run: a success bubble travels upward

Read the text transcript
| Frame | Gap needed | Action |
|---|---|---|
| exists(0,2) | 2 | Wait for take 1 |
| exists(1,1) | 1 | Both children fail |
| exists(0,2), resumed | 2 | Start skip 1 |
| exists(1,2) | 2 | Take 2 |
| exists(2,0) | 0 | Return true |
| exists(1,2), resumed | 2 | Return true without skip |
| exists(0,2), resumed | 2 | Return true |
Only the top frame returns; its parent then resumes at the statement after the recursive call.
Why this is correct
For every position, a witness must either use it or omit it. The recursive OR therefore covers all possibilities. A true branch already proves the answer; both false branches prove no witness from this state. The DP records exactly the same possibilities, merging states when only their sum matters.
Complexity
Recursive enumeration: O(2ⁿ) worst-case time and O(n) auxiliary call-stack space. Early success may reduce work, but does not improve the worst-case bound.
Bounded-sum DP: O(nk) time, O(k) space. Counting and existence use the same state layout but different operations: addition versus logical OR.
Common mistakes and useful tests
- Using a greedy choice fails: [2, 3], k=3 requires skipping 2.
- Returning false immediately after take fails ignores a possible skip witness.
- Checking only contiguous ranges solves a different problem.
- Sharing and mutating one remaining variable across siblings corrupts the search; our arguments are values.
- [2], k=2 → true; [2], k=3 → false; [1, 2], k=2 → true; [4, 3, 9, 2], k=10 → false.
- Negative extension [3, -1], k=2 → true with recursion only.
- Empty input, positive target → false; target zero under the empty-allowed extension → true.
Pattern recognition and next steps
Look for “any selection,” “each position once,” and “is it possible?” Start with take/skip, then compress the sum states. Continue to counting all matching subsequences to see why early return must disappear.
Company research note
No verified exact public candidate report was found for this contract during the 3 October 2026 research pass. No company tag is inferred from generic subset-sum lists.
Final takeaway
Take reduces the gap; skip preserves it. A true child is enough, but one false child is not.
Download all tested Java solutions. These methods use Java 17+; import java.util.* in a standalone program. Use the Java comments and static dry run together to follow each call, return and update.
Practice next
Next lessonGenerate Binary Strings Without Consecutive Ones in JavaCompare a different recursive promise and how its parent resumes.