Introduction

The phrase "sum possible in array" can mean different problems, but the usual interpretation is subset sum: can some subset of the array add up to a target value. That problem is harder than the simpler two-sum problem, so the right solution depends on whether you are choosing exactly two numbers or any number of numbers.

First Clarify Which Problem You Mean

There are two common versions:

• 'two-sum: do any two elements add to the target?'
• 'subset sum: does any subset add to the target?'

The original title is broad, so it helps to make the distinction explicit. If you only need two elements, a hash set is enough. If you need any subset, dynamic programming is the standard exact approach for non-negative targets of moderate size.

Two-Sum Is Easy

For the two-element version, you scan once while tracking complements you need.

1def has_two_sum(nums: list[int], target: int) -> bool:
2    seen = set()
3    for value in nums:
4        if target - value in seen:
5            return True
6        seen.add(value)
7    return False
8
9
10print(has_two_sum([3, 1, 7, 9], 10))  # True
11print(has_two_sum([3, 1, 7, 9], 20))  # False

That runs in linear time and is usually the best answer when the problem truly means two elements.

Subset Sum With Dynamic Programming

For the more general subset-sum version, dynamic programming works well when values are non-negative and the target is not too large.

The idea is simple: track which sums are reachable after processing each number. If sum 9 is already reachable, and the next number is 4, then sum 13 also becomes reachable.

A compact Python implementation uses a set of reachable sums:

1def has_subset_sum(nums: list[int], target: int) -> bool:
2    reachable = {0}
3
4    for value in nums:
5        new_sums = set()
6        for current in reachable:
7            next_sum = current + value
8            if next_sum == target:
9                return True
10            if next_sum < target:
11                new_sums.add(next_sum)
12        reachable |= new_sums
13
14    return target in reachable
15
16
17print(has_subset_sum([3, 34, 4, 12, 5, 2], 9))   # True
18print(has_subset_sum([3, 34, 4, 12, 5, 2], 30))  # False

This style is easy to read and avoids building a full two-dimensional table.

Why the DP Approach Works

Suppose you have already processed some prefix of the array and know which sums are possible. When you see a new value, every existing reachable sum can either:

• stay as it is because you skip the value
• produce a new reachable sum because you include the value

That is exactly the recurrence behind classic subset-sum DP. The set-based version simply stores the reachable sums directly instead of materializing a boolean matrix.

If you prefer the traditional table, the state is usually written as:

• 'dp[i][s] is true if sum s is reachable using the first i numbers'

That version is good for teaching, but in production code the set-based or one-dimensional form is often cleaner.

What About Negative Numbers

Negative values make the problem more subtle because the reachable sum range is no longer bounded between 0 and target. The set-based implementation can still work for small inputs, but the state space may grow much faster.

If negatives are allowed, you should not assume the usual 0..target DP layout is valid. In interviews and programming contests, subset-sum problems often implicitly assume non-negative integers unless stated otherwise.

When Input Size Gets Large

Subset sum is computationally expensive in the general case. That is why there is no one-line trick equivalent to two-sum.

Practical guidance:

• use hash-set logic for two-sum
• use DP for subset sum when the target is moderate
• consider meet-in-the-middle for larger exact subset-sum instances
• consider approximation or problem-specific pruning for very large instances

The right answer depends on the input constraints, not just the title of the problem.

Common Pitfalls

The biggest mistake is solving the wrong problem. Many people implement two-sum when the question allows any subset, or they build subset-sum DP when only two values are needed.

Another mistake is assuming the standard target-bounded DP works with negative numbers. It does not, at least not without changing the state representation.

People also forget that subset sum depends heavily on the target size. An O(n * target) method can be fine for a target of 10000 and completely impractical for a target of 1000000000.

Finally, do not mutate the same reachable set while iterating over it unless you are doing so very carefully. Creating new_sums from the previous state avoids accidental reuse of the current value multiple times.

Summary

• Clarify whether the problem is two-sum or subset sum.
• Two-sum is usually solved in linear time with a hash set.
• General subset sum is commonly solved with dynamic programming.
• Negative numbers require extra care because standard target-bounded DP assumptions break.
• Always choose the algorithm based on the actual constraints, not just the problem title.