DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Combination Sum

mediumRecursion Must-do

Problem statement

You are given an array of distinct positive integers candidates and a positive target. Return every distinct combination of candidates whose values add up to target. The same candidate may be used any number of times.

Two combinations are the same if they use each value the same number of times, so [3, 5] and [5, 3] count once. Return the combinations in any order.

Examples

Example 1

Input: candidates = [3, 4, 5], target = 8

Output: [[3, 5], [4, 4]]

Explanation: 4 can be reused, so 4 + 4 counts.

Example 2

Input: candidates = [2, 3], target = 7

Output: [[2, 2, 3]]

Hints

Approach

Generate each combination in exactly one order: non-decreasing by index. Pass a start index into the recursion and only loop from start onwards. Passing i (not i + 1) into the next call is what allows the same candidate to be reused.

  1. Sort candidates.
  2. dfs(start, remaining): if remaining == 0, record a copy of path.
  3. For i from start: if candidates[i] > remaining, break, because every later value is larger.
  4. Otherwise append it, call dfs(i, remaining - candidates[i]), pop it.

No duplicates are ever produced, so no set and no sorting of results is needed, and the break prunes whole branches. The worst case is still exponential, but the search visits each combination once instead of once per ordering.

ComplexityTime O(N^(T/M)) upper bound, far fewer nodes than the brute force in practiceSpace O(T/M) recursion depth besides the output
Python
class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
candidates = sorted(candidates)
result, path = [], []
def dfs(start: int, remaining: int) -> None:
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining:
break # sorted, so nothing later fits either
path.append(c)
dfs(i, remaining - c) # i, not i + 1: reuse allowed
path.pop()
dfs(0, target)
return result

Follow-up questions

  • Each candidate may be used at most once and the input may contain duplicates. Return distinct combinations.
  • Only count the combinations instead of listing them. (A dynamic programming table over sums does it in O(N · T).)

Frequently asked questions

Recurse with i + 1 instead of i. If the input may also contain duplicates, sort it and skip candidates[i] when it equals candidates[i - 1] and i > start, so equal values do not start the same branch twice.

The early exit relies on every later candidate being at least as large as the current one. Without sorting you could only continue past a too-large value, which still loops over the rest.

Choosing instance sizes that add up to a required capacity, or splitting a batch into chunk sizes from a fixed menu, is a combination sum. The start-index trick is the general way to enumerate multisets without generating each one several times.