494. Target Sum — DSA Atlas

494

MediumOne-Dimensional Dynamic ProgrammingKnapsackPattern-guided

Target Sum

Solve LeetCode #494, “Target Sum.” Read the official prompt once, then return here to turn its requirements into the one-dimensional dynamic programming pattern.

Open official problem prompt ↗

In plain English

Learn how to translate “Target Sum” into a precise state, transition, and stopping condition before committing to code.

Picture it like this

Treat the prompt like a route on a map: One-Dimensional Dynamic Programming is the map legend, the invariant is your current location marker, and each code step must move you closer to the destination without losing what is already known.

Example

Input: Use the first example in the official prompt
Output: Predict the result before reading the explanation
Why: Trace how the one-dimensional dynamic programming invariant transforms the input into the required answer.

Constraints

Identify the input shape and required return valueMark the largest constraint before choosing an approachConfirm that O(amount × coins) is appropriate for that constraint

Pattern lesson

See the pattern, then code

Knapsack

↗

One-Dimensional Dynamic Programming

Count ways or optimize a result where each state depends on earlier positions.. Before computing dp[i], every state used by its transition is already final.

New words, made simpleKnow these before the algorithm

Signal: A phrase or constraint in the prompt that points toward One-Dimensional Dynamic Programming.
State: The smallest set of facts the algorithm must remember while it processes the input.
Invariant: Before computing dp[i], every state used by its transition is already final.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Direct simulation or enumeration

Useful for a tiny example, but compare it with the largest constraint before coding.

Follow the wording literally and try every candidate, using it as a correctness baseline.

Time Usually quadratic or exponentialSpace Problem dependent

Best choiceOne-Dimensional Dynamic Programming pattern

This is the recommended starting structure; adapt its state and return value to the official prompt.

Maintain this invariant: Before computing dp[i], every state used by its transition is already final.

Time O(amount × coins)Space O(amount)

The rule we keep true

Invariant

Before computing dp[i], every state used by its transition is already final.

Why this is correct

Reasoning

The One-Dimensional Dynamic Programming template avoids repeating work by preserving exactly the information needed for the next decision. For “Target Sum,” prove that every update keeps the invariant true and that the final state matches the requested output.

The algorithm in three movesSay these aloud before coding

1Restate the prompt with a tiny hand-made example

Goal: Target Sum

2Name the state maintained by the one-dimensional dynamic programming pattern

Pattern: One-Dimensional Dynamic Programming

3Trace one complete iteration before writing code

Invariant: Before computing dp[i], every state used by its transition is already final.

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

Prompt0

State1

Choice2

Invariant3

Answer4

1 · ReadLeetCode #494: Target Sum

2 · AskWhat are the input, output, and largest constraint?

3 · Update stateTopic = One-Dimensional Dynamic Programming; tier = Knapsack

4 · ResultWrite a one-sentence contract and reject approaches that exceed the constraint.

Key takeaway

Move from the raw prompt to a maintained invariant, then to the final answer.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 1Name the pattern operation
Start from the reusable template, but rename the function and parameters to match the official prompt.
2
Lines 1–3Define the state
Locate the variables or data structure that remember everything needed for the next decision.
3
Lines 4Find the transition
This is where the current input changes the maintained state. Say the update aloud before editing it.
4
Lines 6–8Connect state to the answer
Adapt the template’s generic result to the exact return type and success condition in this problem.
5
Lines 1–8Verify the contract
Trace the official example and confirm the promised O(amount × coins) time and O(amount) space bounds.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Use the smallest input allowed by the prompt.
Try an input where no candidate or transition succeeds, if the contract permits it.
Try duplicate, equal, empty, boundary, or maximum values relevant to the input type.

Common beginner mistakes

Copying the pattern template without adapting its state to this problem’s return value.
Choosing the pattern from the title alone instead of checking constraints and monotonicity.
Stating a complexity without counting every nested loop, data-structure operation, and recursion level.

Check your understanding

Before coding “Target Sum,” what invariant will you maintain, and which line of the prompt makes that invariant useful?

Target Sum

Target Sum

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in One-Dimensional Dynamic Programming