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
Example 1 Case 1
- Input
nums=[1,2,1]; k=2- Output
2
Count two index choices.
Example 2 Case 2
- Input
nums=[2,2]; k=2- Output
2
Equal values at different indexes count separately.
Example 3 Case 3
- Input
nums=[5]; k=3- Output
0
No matching non-empty selection.
Direct match not yet confirmed; opens a GeeksforGeeks search.
Hints Optional
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.
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
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.
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
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

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.
Recognition and related practice
“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 DPCompare a different recursive promise and how its parent resumes.