Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Count Subsequences with Sum K in Java: Choices, Returns, and DP

Understand take-or-skip recursion, non-empty index choices, returned counts, and positive-target dynamic programming with commented Java and a real call tree.

MediumRecursion and backtrackingPattern: recursion, backtracking

Problem statement

Count non-empty subsequences whose elements sum to k. A subsequence preserves input order but may skip values. Different choices of indexes count separately, even if their values look equal.

The original takeUforward prompt uses 1–20 values, each from 1–100, and k from 1–2000. No modulus is specified. There are at most 2²⁰−1 non-empty choices; int fits, but our teaching solution uses long.

For [1, 2, 1], k=2, there are two answers: the middle [2] and the first-plus-last [1, 1]. For [4, 9, 2, 5, 1], k=10, [9, 1] and [4, 5, 1] contribute two.

Constraints & requirements

CONTRACT
Count index selections, not distinct value lists. The empty selection must not count.

Examples 3 test cases

  1. Example 1 Case 1

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

    Count two index choices.

  2. Example 2 Case 2

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

    Equal values at different indexes count separately.

  3. Example 3 Case 3

    Input
    nums=[5]; k=3
    Output
    0

    No matching non-empty selection.

Find on GeeksforGeeks ↗

Direct match not yet confirmed; opens a GeeksforGeeks search.

Hints Optional

Hints become more specific one step at a time.
01Find the smaller problem

Every index has two choices: take or skip.

02Define the state

Carry index, running sum, and whether any value was chosen. A finished valid choice returns 1.

03Connect the recurrence

Add take and skip counts; for bounded positive sums, merge repeated states with descending-sum DP.

How to think before coding

Use the same index/remaining decisions as the existence version, but return a count. Taking index i and skipping it represent disjoint index selections, so add their returned counts instead of OR-ing them. Equal-valued positions remain different selections. For positive bounded sums, tabulate or memoize repeated states; check separately whether an empty selection is allowed.

Understand the choices before the code

The intuition is that every index gives two separate choices: take this element or skip it. Add the counts returned by those two branches.

At index i, choose one of two actions:

  • Take nums[i]: move to i+1 with a larger running sum.
  • Skip nums[i]: move to i+1 with the same sum.

index means “the next undecided position,” not “the last chosen position.” Each call answers: how many valid completions exist from this state?

We do not need to build or copy each subsequence just to count it. A running sum and a flag saying whether anything was chosen are enough.

Baseline: enumerate index masks

For a small array, each nonzero bit mask represents one non-empty selection. Add values whose bits are set.

Java
static long countMasks(int[] nums, int k) {
    long answer = 0; // Count valid non-empty masks.
    for (int mask = 1; mask < (1 << nums.length); mask++) { // Zero is the empty choice.
        long sum = 0; // Start a fresh total for this selection.
        for (int i = 0; i < nums.length; i++) { // Examine every input position.
            if ((mask & (1 << i)) != 0) sum += nums[i]; // Include positions whose bit is one.
        }
        if (sum == k) answer++; // Each matching mask is one distinct subsequence.
    }
    return answer; // This oracle is O(n·2^n), intended for small n.
}

This is clear but repeats additions. Recursion carries the partial sum, reducing the enumeration to O(2ⁿ) work.

Recursive solution: add returned counts

Java
public static long countSubsequences(int[] nums, int k) {
    return countFrom(nums, 0, 0L, false, k); // No index has been decided; no value chosen.
}

private static long countFrom(int[] nums, int index, long sum, boolean chosen, int k) {
    if (index == nums.length) { // Every index now has exactly one take/skip decision.
        return chosen && sum == k ? 1L : 0L; // Count one valid non-empty choice, or none.
    }
    long take = countFrom(nums, index + 1, sum + nums[index], true, k); // Choose this index.
    long skip = countFrom(nums, index + 1, sum, chosen, k); // Leave this index out.
    return take + skip; // Disjoint choices contribute separate counts, even for equal values.
}

Why return 1 or 0 at a leaf? A complete choice either contributes one answer or none. Internal calls add the counts from their two disjoint branches.

Why not return when sum == k before the final index? It makes generalizations with zeros incorrect: later zero-valued indexes can create additional choices. Finishing every index also makes the base-case meaning unambiguous. The linked input is strictly positive, but this recursive version safely handles zeros and negatives too.

Why chosen? The linked k is positive, so the empty subsequence cannot match. The flag makes the non-empty contract explicit and also excludes it when testing k=0 as an extension.

Faster solution for positive, bounded sums

Different decision paths can arrive at the same (index, sum). Dynamic programming reuses those counts. Define ways[s] as the number of selections from processed indexes that sum to s.

Java
public static long countSubsequencesDp(int[] nums, int k) {
    long[] ways = new long[k + 1]; // ways[s] counts choices from already processed indexes.
    ways[0] = 1; // One empty choice starts the construction; k is positive in this problem.
    for (int value : nums) { // Introduce each array position exactly once.
        for (int sum = k; sum >= value; sum--) { // Descend: do not reuse this value twice.
            ways[sum] += ways[sum - value]; // Add choices that become sum by taking value.
        }
    }
    return ways[k] - (k == 0 ? 1 : 0); // Exclude the empty choice in the teaching k=0 extension.
}

Why move sum downward? For value=2 and target=4, an upward pass could update ways[2], then immediately reuse that updated cell to form ways[4] using the same index twice. Descending reads the previous stage for every positive value.

Why ways[0]=1? It is the empty construction that lets the first chosen value start a subsequence. Since the actual target is positive, it never counts as the final answer. The subtraction supports k=0 for the nonnegative extension.

Scope: This array DP requires nonnegative values and k≥0. Do not pass negative values to it; use the general recursion or an appropriately bounded map-based DP. The recursion explains the choices; DP avoids recomputing equal states for these constraints.

Mistakes, tests, and junior-engineer doubts

  • Returning take || skip answers existence, not a count.
  • Deduplicating equal values incorrectly merges different index choices.
  • A global sum needs undo; our numeric sum is passed by value, so siblings do not share it.
  • Stopping at the first match misses additional branches.
  • [2, 2], k=2 → 2; [5], k=3 → 0; [1, 2, 1], k=2 → 2.
  • Extended test [0, 0], k=0 → 3 non-empty choices, not 4; [3, -1], k=2 → 1. Only the recursive method is used for negative tests.

Recursion tree: [1, 2], k=2

Worked example · read from top to bottom
count(i=0,sum=0)
├─ take 1 → count(1,1)
│  ├─ take 2 → count(2,3) returns 0
│  └─ skip 2 → count(2,1) returns 0
│  returns 0+0 = 0
└─ skip 1 → count(1,0)
   ├─ take 2 → count(2,2) returns 1
   └─ skip 2 → count(2,0,chosen=false) returns 0
   returns 1+0 = 1
root returns 0+1 = 1

Only one frame executes at a time. A parent waits for take to return, saves that count, then starts skip. The live stack is one root-to-current path, never every node of the tree at once.

Dry run and repeated values

Numbered illustrated dry run for Count Subsequences with Sum K; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript

For [1, 1, 1], k=2, the valid index sets are {0,1}, {0,2}, and {1,2}. Answer 3, not 1. We count positions; we are not deduplicating value sequences.

index Take branch receives Skip branch receives Parent returns
0, sum=0 index=1, sum=1 index=1, sum=0 take + skip
1, sum=1 index=2, sum=2 index=2, sum=1 counts from both
3, any sum no next choice no next choice 1 if chosen and sum=k, else 0

Annotate each child with its exact numeric return, then add those two numbers in the parent. A selected path alone does not show how the count is accumulated.

Why the recurrence is correct

Every index selection either contains index i or does not. Those groups are exhaustive and disjoint. Recursion counts both, then adds them. The DP transition expresses the same partition: old ways to reach s, plus ways to reach s−value before adding this position.

Complexity

Mask baseline: O(n·2ⁿ) time, O(1) auxiliary space. Recursion: O(2ⁿ) time and O(n) call-stack space. No output list is built.

DP: O(nk) time, O(k) space. It is pseudo-polynomial in the numeric target, not polynomial in its bit length. For n≤20, both recursion and DP are useful; there is no universal dominance when k is very large.

“Count selections, each index used at most once, exact sum” suggests take/skip recursion and then subset-sum DP. It is not a contiguous subarray sum problem.

Compare checking whether a sum exists: same choices, different return type and stopping rule.

Company research note

No sufficiently specific public candidate report for this exact counting contract was verified in this research pass (3 October 2026). Related move-sequence or combination questions are not automatically the same problem, so no company badge is attached.

Final takeaway

Count at the leaves; add at the parents. Equal values can still represent different choices because their indexes differ.

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 lessonDoes a Subsequence with Sum K Exist? Java Recursion and DP

Compare a different recursive promise and how its parent resumes.

Back to Recursion and backtracking →