Combination Sum

Share

Given an array of distinct integers candidates and a target integer, return a list of all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Example 1
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation: 2+2+3 = 7 and 7 = 7 are the only two combinations.
Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Solution Approach

We perform backtracking where at each step we try every candidate starting from the current index (allowing reuse). We subtract the chosen candidate from the remaining target and recurse. When the remaining target hits 0 we record the combination. We prune when the remaining target goes negative.

  • Sort candidates to enable early termination when a candidate exceeds the remaining target.
  • At each recursive call, loop from start to end; if candidates[i] > remaining, break.
  • Add candidates[i], recurse with the same index i (reuse allowed) and remaining - candidates[i].
  • Backtrack by removing the last element.
Java
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int remaining,
                           int start, List<Integer> current,
                           List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break; // pruning
            current.add(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }
}
Complexity Analysis:

Time complexity: O(N^(T/M)) where N is the number of candidates, T is the target, and M is the minimum candidate value.
Space complexity: O(T/M) for the recursion depth.