Check if there exists a subsequence with sum K

Easy

The same branch, returning a boolean

Problem

Return whether any subsequence of the array sums to exactly K.

In simple words

Recurse take-or-skip; return true as soon as any branch hits the target sum.

The idea

Identical recursion, but combine the two branches with OR instead of addition and stop as soon as one succeeds. That short-circuit is a real saving over counting every way.

The trick

Return true immediately from the take branch if it succeeds.
Memoise on (index, target) for the pseudo-polynomial bound.

←→stepspaceplay

1/4

Optimal

timeO(2ⁿ)spaceO(n)

Cut branches past the target.

1function go(i, remaining) {2  if (remaining === 0) return true;3  if (i === n || remaining < 0) return false;4  return go(i + 1, remaining - a[i]) // take5      || go(i + 1, remaining);       // skip6}

Input

array: [2, 3, 5]

Memory

remaining: —

Output

remaining: —
found: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: nums = [1, 2, 3], k = 5
Output:: true
Explanation:: {2,3} sums to 5.

Example 2

Input:: nums = [1, 2, 3], k = 7
Output:: false
Explanation:: Max is 6 → false.

Example 3

Input:: nums = [4], k = 4
Output:: true
Explanation:: The single 4 works.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.