What is the brute force approach and complexity for Combination Sum IV?

Count sequences by recursion: for each number that fits, count the sequences for what is left with time complexity O(N^T) and space complexity O(T).

What is the optimal approach and complexity for Combination Sum IV?

ways[t] = sum of ways[t − x] over every number x, filled for t = 1 … target with optimal time complexity O(T · N) and space complexity O(T).

How do you identify the pattern for Combination Sum IV?

Look for key signals in the prompt: "how many sequences" indicates The goal is a count of ordered sequences. Each total is a sum of counts for smaller totals.; "distinct positive numbers, each one reusable" indicates Unbounded: the same number can be the last number of many different sequences.; "1 + 2 and 2 + 1 are different answers" indicates The order matters, so the totals are the OUTER loop..

Combination Sum IV

Medium·LeetCode #377 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You get a list of distinct positive numbers nums and a number target. Count how many sequences of numbers from nums add up to target. You may use each number as many times as you like.

The order matters here: 1 + 2 and 2 + 1 are two different answers. Return the count.

Input

nums, a list of distinct positive integers, and target, the sum to reach.

Output

The number of ordered sequences of numbers from nums whose sum is target.

Example 1

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

Output: 7

The sequences are 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2 and 3+1. Sequences like 1+2+1 and 2+1+1 count as different answers.

Example 2

Input: nums = [9], target = 3

Output: 0

9 is bigger than 3, so no sequence can make 3.

Constraints

• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 1000
• All the elements of nums are unique.
• 1 ≤ target ≤ 1000
• The test cases are generated so that the answer can fit in a 32-bit integer.

Pattern Recognition Clues

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

“how many sequences”

→ The goal is a count of ordered sequences. Each total is a sum of counts for smaller totals.

“distinct positive numbers, each one reusable”

→ Unbounded: the same number can be the last number of many different sequences.

“1 + 2 and 2 + 1 are different answers”

→ The order matters, so the totals are the OUTER loop.

Approach Complexity Ladder

Brute Force — recurse on the sum left, try every last numberO(N^T)O(T)

Count sequences by recursion: for each number that fits, count the sequences for what is left

Optimal — bottom-up over the total, numbers insideO(T · N)O(T)

ways[t] = sum of ways[t − x] over every number x, filled for t = 1 … target

Brute Force Intuition

To count the sequences that make left, look at the last number of each sequence. For each x ≤ left, count the sequences that make left − x and add them up. The empty sequence makes 0 in exactly one way.

Recognition rule for this sub-pattern:

Items can repeat — capacity loop goes low → high. Order of loops decides combinations vs permutations.

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