Introduction

The phrase "subsequence sum" can refer to several related problems, so the first step is to make the variant explicit. In practice, people usually mean one of these: determine whether some subsequence reaches a target sum, count how many subsequences do, or find an extremal sum such as the maximum over a constrained choice.

Subsequence Versus Subarray

A subsequence keeps the original order but may skip elements. A subarray must be contiguous.

Example sequence:

[3, 1, 4, 1, 5]

Valid subsequence:

[3, 4, 5]

Valid subarray:

[4, 1, 5]

That distinction matters because the algorithms are different. Kadane's algorithm solves a contiguous maximum-subarray problem, not the general "pick any subsequence whose sum matches a target" problem.

Target-Sum Existence With Dynamic Programming

For non-negative integers, a common task is: can some subsequence sum to a target?

1def has_subsequence_sum(nums, target):
2    possible = {0}
3
4    for value in nums:
5        next_possible = set(possible)
6        for current in possible:
7            next_possible.add(current + value)
8        possible = next_possible
9
10    return target in possible
11
12
13print(has_subsequence_sum([3, 1, 4, 1, 5], 9))
14print(has_subsequence_sum([3, 1, 4, 1, 5], 2))

This works by tracking every sum that can be formed after processing each element.

Why the Set-Based DP Works

At each step, every existing achievable sum leads to two choices:

• skip the current value
• include the current value

That means the reachable-sum set grows from earlier decisions, which is exactly what dynamic programming captures well.

This is a good fit for:

• target-sum existence
• small to medium target values
• non-negative sequences

Counting Subsequences With a Given Sum

If you need the number of subsequences, not just existence, store counts instead of booleans.

1from collections import Counter
2
3
4def count_subsequence_sums(nums, target):
5    counts = Counter({0: 1})
6
7    for value in nums:
8        next_counts = Counter(counts)
9        for subtotal, ways in counts.items():
10            next_counts[subtotal + value] += ways
11        counts = next_counts
12
13    return counts[target]
14
15
16print(count_subsequence_sums([1, 2, 3, 3], 6))

This counts how many subsequences produce the target sum, including different index choices that yield the same numeric sum.

Complexity Tradeoffs

Brute force examines all subsequences, which is 2^n. Dynamic programming avoids full enumeration when the state space of sums is manageable.

Still, the DP can become expensive if:

• values are large
• targets are large
• negative numbers make the reachable sum range wide

So the right algorithm depends on the problem constraints, not just on the name "subsequence sum."

Small Example by Hand

For nums = [2, 4, 6] and target 8, the valid subsequence is [2, 6]. The DP reaches that result because:

• start with reachable sum 0
• after 2, reachable sums are 0, 2
• after 4, reachable sums are 0, 2, 4, 6
• after 6, reachable sums include 8

This is the core intuition behind the set-based method: each new number expands the space of reachable sums.

Common Pitfalls

The most common mistake is confusing subsequences with subarrays. If the problem allows skipping elements, contiguous-array algorithms are the wrong tool.

Another issue is ignoring duplicates. Two subsequences with the same numeric values but different positions may count separately depending on the problem definition.

A third pitfall is assuming the simple target-sum DP handles arbitrary negative numbers efficiently. Once negatives are involved, the state space and strategy may need to change.

Finally, be clear whether you want existence, count, minimum length, or maximum sum. Those are different questions that happen to share similar wording.

Summary

• Subsequence-sum problems come in several variants, so define the exact goal first.
• A subsequence may skip elements; a subarray may not.
• Dynamic programming is a standard approach for target-sum existence and counting.
• The best method depends on value ranges, duplicates, and whether negatives are allowed.
• Do not apply contiguous-array algorithms to general subsequence problems by mistake.