Combination Sum

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given an array of distinct positive integers candidates and a positive target, return every unique combination of candidates whose sum is exactly target. Each number may be used any number of times. Two combinations are the same if they use the same numbers the same number of times, in any order, so [3, 5] and [5, 3] count once. The result may be in any order.

    The standard "backtracking with reuse" problem. It checks that you can enumerate combinations without producing the same one in different orders, and that you prune the search instead of exploring hopeless branches. Original problem: LeetCode 39.

    Example

    With 3, 4 and 5 there are exactly two ways to make 8. Repeating 3 overshoots: 3 + 3 = 6 and 3 + 3 + 3 = 9.
    With 3, 4 and 5 there are exactly two ways to make 8. Repeating 3 overshoots: 3 + 3 = 6 and 3 + 3 + 3 = 9.
    Input:  candidates = [3, 4, 5], target = 8
    Output: [[3, 5], [4, 4]]
    Input:  candidates = [2, 7], target = 11
    Output: [[2, 2, 7]]
    Input:  candidates = [6], target = 4
    Output: []

    Constraints (assumed)

    • 1 ≤ candidates.length ≤ 30; 2 ≤ candidates[i] ≤ 40, all distinct.
    • 1 ≤ target ≤ 40; the number of answers is small (under a few hundred).

    What this question tests

    • Writing a backtracking function with a clear choose / explore / un-choose structure.
    • Avoiding duplicate combinations with a start index instead of a set of results.
    • Pruning with sorted input, and knowing the output-sensitive complexity.

    Questions to ask first

    1. Can a number be reused? (Here: yes, unlimited times. Combination Sum II allows each once.)
    2. Are the candidates distinct and positive? Zero or negative numbers would make the search infinite. (Here: distinct and positive.)
    3. Does the order of numbers inside a combination matter? (Here: no; [3, 5] = [5, 3].)
    4. Do you need the combinations or just how many there are? Counting is a DP problem and much faster.