What is the brute force approach and complexity for Target Sum?

Recurse on each number with a + or a −; count the sign patterns whose total is the target with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for Target Sum?

P = (total + target) / 2; check it is a whole number in range, then count subsets with sum P with optimal time complexity O(N · S) and space complexity O(S).

How do you identify the pattern for Target Sum?

Look for key signals in the prompt: "put a + or − before each number" indicates Each number is a 0/1 choice: + group or − group. That is the same shape as a subset.; "the expression evaluates to target" indicates A sum rule on the two groups: P − N = target, and P + N = total.; "the number of ways" indicates Count the ways, do not check one. After the split, count subsets with sum P..

Target Sum

Medium·LeetCode #494 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You get a list of numbers nums and a number target. Put a + or a - in front of every number, then add all of them up.

Count how many ways of choosing the signs make the total equal to target.

Input

nums, a list of non-negative integers, and target, an integer.

Output

The number of ways to put a + or - before each number so that the total is target.

Example 1

Input: nums = [1, 1, 1, 1, 1], target = 3

Output: 5

The minus sign can go on any one of the five 1s, which gives five ways: for example −1 + 1 + 1 + 1 + 1 = 3.

Example 2

Input: nums = [1], target = 1

Output: 1

Only +1 gives 1.

Example 3

Input: nums = [1, 2], target = 4

Output: 0

The biggest total is 1 + 2 = 3, so 4 cannot be reached.

Constraints

• 1 ≤ nums.length ≤ 20
• 0 ≤ nums[i] ≤ 1000
• 0 ≤ sum(nums) ≤ 1000
• −1000 ≤ target ≤ 1000

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“put a + or − before each number”

→ Each number is a 0/1 choice: + group or − group. That is the same shape as a subset.

“the expression evaluates to target”

→ A sum rule on the two groups: P − N = target, and P + N = total.

“the number of ways”

→ Count the ways, do not check one. After the split, count subsets with sum P.

Approach Complexity Ladder

Brute Force — try + and − for every numberO(2^N)O(N)

Recurse on each number with a + or a −; count the sign patterns whose total is the target

Better — memo on (index, running sum)O(N · S)O(N · S)

The same recursion, but remember each (index, running sum) pair so it is solved only once

Optimal — split into + and − groups, count subsets with sum PO(N · S)O(S)

P = (total + target) / 2; check it is a whole number in range, then count subsets with sum P

Brute Force Intuition

Each number gets a + or a -. Walk the numbers in order and try both signs for each one. When every number has a sign, check whether the total equals target. Each sign pattern is exactly one path, so the paths that end at the target are the answer.

Recognition rule for this sub-pattern:

Same table, but add counts instead of taking a max.

Remember this · DP — Knapsack

Trigger

Pick a subset to hit a target sum / capacity, partition into two groups, count the ways to reach an amount.

Think

Is this "choose some items so their total is X"?

Key question

Can each item be used once (loop capacity backwards) or many times (loop forwards)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Knapsack translate into production architectures and low-level memory mechanics.

LLD Architecture