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

Check every subset of 1…9; keep the ones with k numbers and sum n with time complexity O(9 · 2⁹) and space complexity O(1).

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

Pick numbers in increasing order; stop at k numbers, and stop when the sum would pass n with optimal time complexity O(2⁹ + A · k) and space complexity O(k).

Combination Sum III

Q: How do you identify the pattern for Combination Sum III?

Look for key signals in the prompt: "k different numbers" indicates A set of k numbers with no repeats: choose K, with an increasing start index.; "numbers 1 through 9" indicates A small fixed pool, so the search tree has at most 512 nodes.; "add up to n" indicates A sum target. Carry the running sum down, and prune when it goes past n.; "each number at most once" indicates Recurse on i + 1, not i. Reusing a number is not allowed..

Medium·LeetCode #216 Pro OnlySlight Variation

LeetCode

Problem Statement

You need a set of k different numbers, chosen from 1 to 9, whose sum is exactly n. Each number can be used at most once.

Return every set that works. Each set is a list of k numbers. Sets can come back in any order, but no set may appear twice.

Input

Two integers, k and n.

Output

A list of all valid sets. Each set has k numbers, and they add up to n.

Example 1

Input: k = 3, n = 7

Output: [[1,2,4]]

1 + 2 + 4 = 7. No other set of three different numbers adds up to 7.

Example 2

Input: k = 3, n = 9

Output: [[1,2,6],[1,3,5],[2,3,4]]

Each of these three sets has three different numbers that add up to 9.

Example 3

Input: k = 4, n = 1

Output: []

The smallest four different numbers are 1 + 2 + 3 + 4 = 10, which is already more than 1. So there are no answers.

Constraints

• 2 ≤ k ≤ 9
• 1 ≤ n ≤ 60

Pattern Recognition Clues

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

“k different numbers”

→ A set of k numbers with no repeats: choose K, with an increasing start index.

“numbers 1 through 9”

→ A small fixed pool, so the search tree has at most 512 nodes.

“add up to n”

→ A sum target. Carry the running sum down, and prune when it goes past n.

“each number at most once”

→ Recurse on i + 1, not i. Reusing a number is not allowed.

Approach Complexity Ladder

Brute Force — try all 512 sets of numbers 1…9O(9 · 2⁹)O(1)

Check every subset of 1…9; keep the ones with k numbers and sum n

Optimal — increasing picks with a start index and two prunesO(2⁹ + A · k)O(k)

Pick numbers in increasing order; stop at k numbers, and stop when the sum would pass n

Brute Force Intuition

Each number from 1 to 9 is in the set or out of it. That gives 2⁹ = 512 subsets. Keep a subset only if it has exactly k numbers and its numbers add up to n.

Recognition rule for this sub-pattern:

Choose K items in increasing index order so the same group is never generated twice.

Remember this · Backtracking

Trigger

"All subsets / permutations / combinations", place items under rules (N-Queens, Sudoku), find a path in a grid.

Think

At each step, what are my choices, and how do I undo a choice?

Key question

What is my state, when is it complete, and when do I prune?

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 Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture