Count Subsequences with Sum K

New·Medium·Recursion

How many subsequences add up to the target

Asked at:AmazonGoogleMicrosoft

Practice mode

Step

Initialization

Every leaf that lands exactly on sum = 0 contributes 1. Counts are summed on the way back up, so the root ends up holding the total across the whole tree.

Recursion workspace

Take / Skip Recursion

Step 1 / 28init

100%

nums

[1,3,2]

sum

f(0, 3)start

each call: take nums[i] → sum − nums[i], or skip it → sum · sum = 0 → 1, else 0 · counts add on the way up

Explanation

Same take / skip split as the existence version, but the branches add their counts instead of short-circuiting — so the whole tree must be explored.

step 1 / 28

Space play← → stepHome reset

TimeO(2ⁿ)·SpaceO(n)

Take / Skip Recursion

1function func(ind, sum, nums) {
2  // One valid subsequence
3  if (sum === 0) return 1;
4 
5  // Overshot, or ran out of elements
6  if (sum < 0 || ind === nums.length) return 0;
7 
8  // Include nums[ind]
9  const take = func(ind + 1, sum - nums[ind], nums);
10 
11  // Exclude nums[ind]
12  const notTake = func(ind + 1, sum, nums);
13 
14  return take + notTake;
15}
16 
17function countSubsequenceWithTargetSum(nums, target) {
18  return func(0, target, nums);//target: 3
19}

target3

Command Palette

Count Subsequences with Sum K

Count Subsequences with Sum K