Subsequence Sum Exists

New·Medium·Recursion

Does any subsequence add up to the target?

Asked at:AmazonMicrosoftAdobe

Practice mode

Step

Initialization

At each index, branch twice — take the element (subtract it from k) or skip it. Because the branches are OR-ed, the search stops the moment one path reaches 0.

Recursion workspace

Take / Skip Recursion

Step 1 / 16init

100%

nums

[1,4,2]

f(0, 3)start

each call: take nums[i] → k − nums[i], or skip it → k · k = 0 → true, k < 0 → false · || stops at the first true

Explanation

Ask the same question at every index: can the rest of the array make up what is left of k? Taking an element subtracts it from k; reaching 0 is success, going below 0 overshoots.

step 1 / 16

Space play← → stepHome reset

TimeO(2ⁿ)·SpaceO(n)

Take / Skip Recursion

1function solve(i, n, arr, k) {
2  // Target met
3  if (k === 0) return true;
4 
5  // Overshot
6  if (k < 0) return false;
7 
8  // Ran out of elements
9  if (i === n) return k === 0;
10 
11  // Take arr[i], or skip it
12  return solve(i + 1, n, arr, k - arr[i]) ||
13         solve(i + 1, n, arr, k);
14}
15 
16function checkSubsequenceSum(nums, target) {
17  const n = nums.length;
18  return solve(0, n, nums, target);//n: 3target: 3
19}

target3

Command Palette

Subsequence Sum Exists

Subsequence Sum Exists