Subsequence with Sum K

You're given an array of positive integers arr and a target k. Return true if some subsequence of arr has elements that sum to exactly k, and false otherwise.

A subsequence is what's left after you delete zero or more elements from the array — for each element you either keep it or drop it, and the kept elements stay in their original order. Every element can be used at most once.

Since a sum doesn't care about order, the real question is: can you choose some subset of the elements whose total is exactly k?

Hints

· Stuck? Reveal one nudge at a time.

For every element you face the same tiny decision. What is it — and how many ways can the whole array be decided?

Take it or leave it: recursing on both choices at every index enumerates every subsequence. Track only how much of k is still needed.

Many branches arrive at the same (index, remaining) state — cache those answers, or flip the question and build a boolean table of which totals from 0 to k are reachable.

Common doubts

No. A subarray is contiguous; a subsequence just keeps relative order and may skip elements. And since a sum ignores order entirely, this problem is really about choosing a subset of elements.

No — each element is a one-shot take-or-skip decision. Allowing reuse turns this into a different (unbounded) problem, and it is exactly why the optimal DP sweeps its sums downward.

It sums to 0, and since k >= 1 it can never be the answer here. But sum 0 being reachable is the seed of every solution — it is why reachable[0] starts as true.

Take arr = [6, 5, 3] with k = 8: greedily grabbing the largest note 6 leaves 2, which nothing fits — yet 5 + 3 = 8. Local best picks can lock you out of the exact total; you need to explore or tabulate.

Interview follow-ups

· What an interviewer asks next.

Both prunes break: an overshoot can recover, so remaining < 0 is no longer terminal, and reachable sums are no longer bounded by k. You would key the DP by a hash map of reachable sums, or use meet-in-the-middle for small n.

Identical states, different value: store counts instead of booleans — dp[s] += dp[s - num] with the same downward sweep. Existence is just the count-question asked as a yes/no.

Yes — either record the take/skip choice per memo state and replay it, or walk the DP table backwards from k, greedily undoing any num with reachable[k - num] set in the previous row.

The O(n * k) table becomes infeasible — the DP is pseudo-polynomial. For small n (around 40) you would split the array in half, enumerate each half's 2^(n/2) sums, and match them with a sorted lookup: meet in the middle.

Fun facts

This is the decision version of Subset Sum — one of the 21 problems Richard Karp proved NP-complete in 1972. The DP still solves it fast because it is pseudo-polynomial: quick when k is small, hopeless when k has many digits.
The reachable-totals row compresses into a bitset: adding a number becomes bits |= bits << num, lighting 64 totals per CPU instruction.
The same take-or-skip skeleton powers Partition Equal Subset Sum, Target Sum, and the whole 0/1 knapsack family — learn it once, reuse it for years.

Asked at

AmazonMicrosoftGoogleFlipkartAdobe

Frequently Sometimes Occasionally

Example 1

Input: arr = [10, 1, 2, 7, 6, 1, 5], k = 8
Output: true
Several picks work: [1, 7] sums to 8, and so does [2, 6].

Example 2

Input: arr = [2, 3, 5, 7, 9], k = 100
Output: false
Even taking every element only reaches 2 + 3 + 5 + 7 + 9 = 26.

Constraints

- 1 <= arr.length <= 2000 - 1 <= arr[i] <= 1000 - 1 <= k <= 2000

This is the gateway problem of the subsequence pattern: one tiny take-it-or-leave-it decision per element, repeated n times, quietly generates every subsequence there is. Master the decision tree here, then watch the same skeleton solve the entire knapsack family.

Prerequisites

Before you start

· Concepts used directly in the solution.

Recursion with choices. Writing a function that branches once per option and trusting it to explore every path for you.

Subsequence vs subarray. A subsequence keeps relative order but need not be contiguous; a subarray must be contiguous. For a sum, only the chosen set matters.

Memoization. Caching a function's answer keyed by its arguments so a state that repeats is solved only once.

Understand the problem

In plain English: pick any subset of the array's elements (keep them or skip them, one decision each). Formally: return true if there exist indices i1 < i2 < … < im such that arr[i1] + arr[i2] + … + arr[im] = k.

Worked example 1 — arr = [10, 1, 2, 7, 6, 1, 5], k = 8

pick 1 and 7  →  1 + 7 = 8  ✓
pick 2 and 6  →  2 + 6 = 8  ✓
answer: true (one way is enough)

Worked example 2 — arr = [2, 3, 5, 7, 9], k = 100

even the whole array: 2 + 3 + 5 + 7 + 9 = 26 < 100
answer: false

Clarifying questions

Asking two or three sharp questions before coding shows an interviewer you design around guarantees instead of discovering them mid-bug.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Are all elements positive, or can they be negative or zero?”

Everything here hinges on positivity: once a running total exceeds k it can never come back down, which unlocks pruning and bounds the DP table at k. Negatives break both.

“Can an element be used more than once?”

No — take-or-skip, once each. If reuse were allowed this becomes a different (unbounded) problem with a different loop direction.

Edge cases

“What if the array has a single element?”

The answer is simply whether that element equals k — a great sanity test for your base cases.

“Does the empty subsequence count as a valid pick?”

It sums to 0, and k is at least 1, so it can never be the answer — but sum 0 being reachable is the seed every solution grows from.

Constraints & scale

“How large can n and k get?”

Up to 2000 each. 2^n subsequences is unthinkable, but an n times k table is only about 4 million cells — that number is the whole strategy.

The ideal opening — say it like this

Before I code, I want to confirm a few guarantees.

Are all the elements positive? If so, a running total that overshoots k is dead and I can prune it.

Each element is usable at most once, correct?

And with n and k both up to 2000, I'm aiming for an n-times-k solution rather than enumerating subsequences.

Key observations

1Aha

Every subsequence is a chain of take-or-skip decisions

Stand on each element once and make one binary choice. Two options per element, n elements — the decision tree's leaves are exactly the 2^n subsequences. Recursion walks this tree for free.

              (i=0, need 8)
             /             \
        take 10           skip 10
    (i=1, need -2) ✗    (i=1, need 8)
                        /          \
                   take 1         skip 1
               (i=2, need 7)   (i=2, need 8) …

2Aha

Only the remaining target matters — not how you got there

Two different paths that both arrive at index i still needing 7 have identical futures. The history of which elements produced that state is irrelevant. So the tree's 2^n paths collapse into at most n * (k + 1) distinct states (i, remaining) — solve each once, remember the answer.

3Aha

Flip the question: which totals are reachable at all?

Instead of chasing one target down a tree, keep a board of totals 0…k and light up every total you can build. Start with 0 lit (the empty pick). Each new number num lights s wherever s - num was already lit. Because all elements are positive, the board never needs a slot above k — anything bigger can never shrink back. The moment slot k lights up, the answer is true.

Brute force vs optimal

	Brute force	Memoization	Optimal
Time	O(2^n)	O(n · k)	O(n · k)
Space	O(n) recursion	O(n · k)	O(k)

The full, runnable code for each step of the arc lives in the Approaches selector below.

Summary

Key takeaway

Take-or-skip recursion enumerates every subsequence; noticing that only (index, remaining) matters collapses it into a table of reachable sums. That collapse is the subset-sum pattern — the seed of the entire knapsack family.

reachable = bool array of size k+1;  reachable[0] = true
for each num in arr:
    for s from k down to num:
        if reachable[s - num]: reachable[s] = true
    if reachable[k]: return true
return reachable[k]