Abstract / Summary

Find the longest subsequence of the given list of integers whose sum equals the target value.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 40% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding the maximum length of a subsequence whose elements sum exactly to a given target. It processes the input list nums sequentially, maintaining a mapping from achievable sums to the longest subsequence length that yields each sum. By the end of the iteration, the mapping either contains the desired target sum with its optimal length or indicates that the target is unattainable.

Core Logic

The algorithm begins by initializing a dictionary named todo that records the base case: a sum of 0 can be achieved with a subsequence of length 0.

todo = {0: 0}

The main loop iterates over each number n in nums. For each element, a fresh copy of the current state is created to represent subsequences that do not include n.

for n in nums:
    next = todo.copy()

The inner loop examines every existing (total, length) pair in todo. For each pair, it checks whether adding the current number n would keep the sum within the allowed target. If the condition holds, it constructs a new candidate subsequence by incrementing both the sum and the length.

    for total, length in todo.items():
        if total + n <= target:
            length += 1
            total += n

When a new sum total is generated, the algorithm ensures that the dictionary next stores the longest possible subsequence for that sum. If the sum is not yet present or the new length exceeds the previously recorded length, the entry is updated.

            if total not in next or next[total] < length:
                next[total] = length

After processing all combinations for the current number, todo is replaced with next, thereby advancing the state to include the effects of n.

    todo = next

Finally, the method returns the length associated with target if it exists; otherwise, it returns -1 to signal impossibility.

return todo[target] if target in todo else -1

Edge Cases Handled

When the input list nums is empty, the initial dictionary contains only the zero-sum entry. The loop body never executes, and the final lookup correctly returns 0 for a target of 0 or -1 for any positive target, reflecting that no subsequence can be formed.

If target itself is 0, the base case entry {0: 0} guarantees an immediate successful result, regardless of the contents of nums.

Numbers larger than target are automatically ignored because the condition total + n <= target prevents them from contributing to any new sum. This prevents unnecessary growth of the state space.

When multiple distinct subsequences lead to the same sum, the algorithm retains only the one with the greatest length. The conditional update if total not in next or next[total] < length ensures that shorter alternatives are discarded, preserving the optimal answer for each intermediate sum.

Duplicate values in nums are treated independently; each occurrence can be either taken or skipped, and the dictionary copy mechanism guarantees that both possibilities are explored without interference.

Performance Optimizations

The use of a dictionary to map sums to lengths provides constant-time access for updates and lookups, enabling the algorithm to avoid scanning the entire list of possible sums on each iteration.

Creating next as a shallow copy of todo before the inner loop isolates the “exclude-current-element” scenario, allowing the algorithm to update only the entries that involve the current number. This avoids the need for a separate data structure to track excluded paths.

The guard if total + n <= target prunes any branch that would exceed the target sum, thereby limiting the number of entries that need to be considered and preventing the state from ballooning with irrelevant sums.

By updating the dictionary only when a longer subsequence is found for a particular sum, the implementation eliminates redundant work and ensures that each sum is associated with the best possible length at any point in the computation.

Overall, the combination of dictionary-based memoization, selective copying, and early pruning yields an efficient traversal of the solution space while maintaining clarity of intent.

Imagine a giant basket of numbered blocks. The goal is to pick out just a few blocks that add up to a specific magic secret number without going over. To solve this, the code uses a magical notebook to remember every possible way to reach different sums.

First, the notebook starts with one page that says if you choose nothing at all, you have a sum of zero and zero blocks. As the code looks at each block in the basket one by one, it opens the notebook to see what combinations it already knows. For every combination it has written down, it thinks about what would happen if it added the new block to that pile.

When a new block is added to a previous pile, the sum gets bigger and the count of blocks increases by one. If this new total is still small enough to fit within the target, the code checks its notebook again. It asks if there is already a way to reach this same total using a different number of blocks. If the new way uses more blocks to reach that same sum, the code scribbles it down because having more blocks is the winning strategy.

Once all the blocks have been looked at, the code turns to the very last page of the notebook to find the secret target number. It looks for the biggest number of blocks associated with that sum, and that becomes the final answer. If the target number is not in the notebook at all, that means it was impossible to make that sum, and the code simply says it could not find a way.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java	C++		Python	TS
	WalkCCC	Java	C++		Python
	leetcode.ca	Java	C++	Go	Python	TS
	Progiez	Java	C++		Python
github	charles-wangkai	Java
	fsq		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality