LeetCode 39. Combination Sum

Posted on In , Views:

🧩 Problem Description

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.

You may choose the same number from candidates an unlimited number of times.
Two combinations are unique if the frequency of at least one number is different.

Return the combinations in any order.

💬 Example

1
2
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
1
2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

💡 Approach: Backtracking with Start Index

  • Sort candidates (optional, helps early pruning).
  • Use DFS to build combinations:
    • Maintain start index to avoid permutations of the same combination.
    • At each step, you can reuse the same index (unlimited usage).
    • If sum == target, push the current path.
    • If sum > target, backtrack (prune).

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // optional but useful for pruning
        List<List<Integer>> res = new ArrayList<>();
        dfs(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void dfs(int[] cand, int remain, int start, List<Integer> path, List<List<Integer>> res) {
        if (remain == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < cand.length; i++) {
            int val = cand[i];
            if (val > remain) break; // prune
            path.add(val);
            dfs(cand, remain - val, i, path, res); // i (not i+1) allows reuse
            path.remove(path.size() - 1);
        }
    }
}

⏱ Complexity Analysis

Let N = len(candidates), T = target, and assuming reasonable pruning:

  • Time: ~O(number of valid combos) in practice; upper bound often expressed as O(N^(T/minVal)) in worst cases.
  • Space: O(T/minVal) recursion depth + output size.

✍️ Summary

  • Classic unbounded knapsack (combinations) via backtracking.
  • Use a start index to avoid duplicate permutations.
  • Prune when the partial sum exceeds target.

Related problems:

  • lc-40 — Combination Sum II (each number used at most once, with duplicates)
  • lc-216 — Combination Sum III
  • lc-377 — Combination Sum IV (order matters, DP)