Combination Sum

Problem Link

Problem: Combination Sum

Problem Statement

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 reuse the same number an unlimited number of times.

Return the combinations in any order.

Examples

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

Example 2
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 500

Intuition

This is a combinatorial generation problem. We need to explore all combinations that sum up to the target.

We use input-output recursion where:

Input is the current index and remaining target
Output is the current list of chosen elements

We recurse over each element and choose to:

Include it (and stay at same index, since repetition is allowed)
Exclude it (move to next index)

Input-Output Recursive Method with Backtracking

Function Signature

void findNumbers(List<List<Integer>> list, List<Integer> arr, int target, int ind, List<Integer> temp)

Parameters

list: final result list
arr: sorted list of distinct candidates
target: remaining target sum
ind: current index in arr
temp: current combination being built

Base Case

If target == 0:

We’ve built a valid combination → add a deep copy of temp to result list.

Recursive Case

Loop from index ind to end:

If arr[i] <= target, include arr[i] in temp
Recurse with reduced target and same index i (as repetition is allowed)
Backtrack by removing last element

Code (Java)

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> inAns = new ArrayList<>();

        // Remove duplicates (defensive) and sort
        Set<Integer> set = new HashSet<>();
        for (int i : candidates) set.add(i);
        List<Integer> candi = new ArrayList<>(set);
        Collections.sort(candi);

        findNumbers(ans, candi, target, 0, inAns);
        return ans;
    }

    public void findNumbers(List<List<Integer>> list, List<Integer> arr, int target, int ind, List<Integer> temp) {
        if (target == 0) {
            list.add(new ArrayList<>(temp));
            return;
        }

        for (int i = ind; i < arr.size(); i++) {
            int val = arr.get(i);
            if (target - val >= 0) {
                temp.add(val);
                findNumbers(list, arr, target - val, i, temp); // reuse same index
                temp.remove(temp.size() - 1); // backtrack
            }
        }
    }
}

Time and Space Complexity

Time Complexity: O(2^target) in worst case
- Each number can either be included or not → exponential choices
Space Complexity:
- O(target) recursion depth
- O(∑k) where k is the average size of combinations

Dry Run

Input: `candidates = [2, 3], target = 5`

Start: target = 5, temp = []

Explore:

Choose 2 → target = 3 → [2]
- Choose 2 → target = 1 → [2,2]
  - Choose 2 → target = -1 → stop
- Choose 3 → target = 0 → [2,3] → valid
Choose 3 → target = 2 → [3]
- Choose 3 → target = -1 → stop

Answer: [[2,3]]

Conclusion

This problem is an excellent example of the input-output recursive model with backtracking, where we control combinations with repetition. It demonstrates how recursion can efficiently enumerate valid combinations under constraints.