Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Does a Subsequence with Sum K Exist? Java Recursion and DP

Learn why existence uses short-circuit returns, how take and skip reduce the remaining target, and how bounded subset-sum DP avoids repeated work.

MediumRecursion and backtrackingPattern: recursion, backtracking

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

  1. Example 1 Case 1

    Input
    nums=[1,2]; k=2
    Output
    true

    The witness requires skipping the first value.

  2. Example 2 Case 2

    Input
    nums=[4,3,9,2]; k=10
    Output
    false

    Both choices must fail before false.

  3. Example 3 Case 3

    Input
    nums=[2]; k=2
    Output
    true

    The last value can close the gap.

Solve on GeeksforGeeks ↗

Hints Optional

Hints become more specific one step at a time.
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:

Java
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

Java
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:

Worked example · read from top to bottom
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

Numbered illustrated dry run for Does a Subsequence with Sum K Exist? Java Recursion and DP; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
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 Java

Compare a different recursive promise and how its parent resumes.

Back to Recursion and backtracking →