Leetcode 39 Combination Sum

Source: Dev.to

Problem Statement

Given an array of distinct integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target.
You may use each candidate an unlimited number of times. Two combinations are considered different if the frequency of at least one number differs.

Example: [2,3,3], [3,2,3], and [3,3,2] represent the same unique combination.

Example

Input

candidates = [2,3,5]
target = 8

Output

[[2,2,2,2], [2,3,3], [3,5]]

Mathematical Formulation

The problem can be expressed as finding non‑negative integers x, y, z such that

2·x + 3·y + 5·z = 8

Solution

class Solution:
    def combinationSum(self, candidates, target):
        results = []

        def backtrack(remain, comb, start):
            if remain == 0:
                # found a valid combination
                results.append(list(comb))   # make a shallow copy
                return
            if remain < 0:
                # exceeded the sum, stop exploring this path
                return

            for i in range(start, len(candidates)):
                # choose the candidate
                comb.append(candidates[i])
                # explore further with the same start index (allow reuse)
                backtrack(remain - candidates[i], comb, i)
                # backtrack
                comb.pop()

        backtrack(target, [], 0)
        return results

Common Pitfalls

Depth‑First Search Walkthrough

The recursion tree for the example (candidates = [2,3,5], target = 8) is illustrated below (each node shows i – index, v – value, remain, and start).

root (target: 8)
└── [i:0, v:2] remain: 6, start: 0
    ├── [i:0, v:2] remain: 4, start: 0
    │   ├── [i:0, v:2] remain: 2, start: 0
    │   │   ├── [i:0, v:2] remain: 0, start: 0 ── Success → [2,2,2,2]
    │   │   ├── [i:1, v:3] remain: -1 ── Fail
    │   │   └── [i:2, v:5] remain: -3 ── Fail
    │   ├── [i:1, v:3] remain: 1, start: 1
    │   │   ├── [i:1, v:3] remain: -2 ── Fail
    │   │   └── [i:2, v:5] remain: -4 ── Fail
    │   └── [i:2, v:5] remain: -1 ── Fail
    ├── [i:1, v:3] remain: 3, start: 1
    │   ├── [i:1, v:3] remain: 0 ── Success → [2,3,3]
    │   └── [i:2, v:5] remain: -2 ── Fail
    └── [i:2, v:5] remain: 1, start: 2
        └── [i:2, v:5] remain: -4 ── Fail
└── [i:1, v:3] remain: 5, start: 1
    ├── [i:1, v:3] remain: 2, start: 1
    │   ├── [i:1, v:3] remain: -1 ── Fail
    │   └── [i:2, v:5] remain: -3 ── Fail
    └── [i:2, v:5] remain: 0 ── Success → [3,5]
└── [i:2, v:5] remain: 3, start: 2
    └── [i:2, v:5] remain: -2 ── Fail

Reference Table