39. Combination Sum

Edited by Charles

Medium · Python · Backtrack

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Recall 216. Combination Sum III for the core idea of the backtrack algorithm. The most fabulous part in this solution is multiple usage of the same number is permitted, and thus, in each recurrence, there is no need to parse i + 1 to the startIndex, and we should allow to parse i to the startIndex, instead.

Original study notes follow, including intermediate snippets and earlier attempts.

Note:

1. Recall 216. Combination Sum III for the core idea of the backtrack algorithm.
2. The most fabulous part in this solution is multiple usage of the same number is permitted, and thus, in each recurrence, there is no need to parse i + 1 to the startIndex, and we should allow to parse i to the startIndex, instead.
3. Additionally, recall 15. 3Sum for a pruning.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	January 22, 2026

Python solution

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        self.backtrack(candidates, target, 0, 0, [], result)
        return result

    def backtrack(self, candidates, targetSum, startIndex, curSum, path, result):
        if targetSum < curSum:
            return

        if targetSum == curSum:
            result.append(path[:])
            return

        for i in range(startIndex, len(candidates)):
            curSum += candidates[i]
            path.append(candidates[i])
            self.backtrack(candidates, targetSum, i, curSum, path, result)
            curSum -= candidates[i]
            path.pop()

---

Back to Day 20 Backtrack II · All Algorithm notes