Combination Sum

Description

Combination Sum
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 return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the

of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

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

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

Constraints:

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

Approach

• We are maintaining List where we keep adding new number to and check if we reach target if yes then add it to the result otherwise we remove the element anyway next regardless
• We pick an element then we iterate starting from that element or something

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        d(0,ans,new ArrayList<>(),0,candidates,target);
        return ans;
    }
 
    public void d(int i, List<List<Integer>> a, List<Integer> curr, int t, int[] c, int target) {
        if (t ==  target) {
            a.add(new ArrayList<>(curr));
            return;
        }
 
        for (int j = i; j < c.length; j++) {
            if (t + c[j] > target) {
                return;
            }
            curr.add(c[j]);
            d(j,a,curr,t + c[j],c,target);
            curr.remove(curr.size()-1);
        }
    }
}

• We used sorting so once we know that the total exceeded we can return and no need to check further
• If we want to not use sorting then use continue instead of return
• If we only add c then any later modification would change in the answer as well that is why we create a copy of it and store in the solution

class Solution {
    List<List<Integer>> a;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        a = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(0,0,new ArrayList<>(),candidates,target);
        return a;
    }
 
    public void dfs(int i, int total, List<Integer> c, int[] n, int target) {
        if (total == target) {
            a.add(new ArrayList<>(c));
            return;
        }
 
        for (int j = i; j < n.length; j++) {
            if (total + n[j] > target)
                return;
 
            c.add(n[j]); //Add element and then check
            dfs(j,total + n[j],c,n,target);
            c.remove(c.size() - 1); // remove element after checking    
        }
    }
}

Brute Force Approach: Standard Include / Exclude Recursion

Intuition

At each candidate element, we make two binary choices:

1. **Include candidates[index]**: Add it to current and keep index the same (allowing it to be chosen again).
2. **Exclude candidates[index]**: Move to index + 1 to process the remaining elements.

We explore all branches until target == 0 (valid path) or target < 0 / index == candidates.length (invalid path).

import java.util.*;
 
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), result);
        return result;
    }
 
    private void backtrack(int[] candidates, int index, int target, List<Integer> current, List<List<Integer>> result) {
        // Base Cases
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (index == candidates.length || target < 0) {
            return;
        }
 
        // Choice 1: Include candidates[index] (stay at same index to reuse)
        current.add(candidates[index]);
        backtrack(candidates, index, target - candidates[index], current, result);
        current.remove(current.size() - 1); // Backtrack
 
        // Choice 2: Exclude candidates[index] (move to next index)
        backtrack(candidates, index + 1, target, current, result);
    }
}
 

Complexity

• Time Complexity: $O(2^T)$, where $T=\text{target}/\min (\text{candidates})$. Every decision node splits into 2 recursive calls up to max recursion depth $T$.
• Space Complexity: $O(T)$ auxiliary stack space for the recursion depth.

---

Most Optimized Solution: Sorted Array + For-Loop Backtracking with Early Pruning

Intuition

Instead of exploring invalid paths down to target < 0, we can optimize by sorting the candidates array first:

1. Iterate with a For-Loop: Start the loop from index start. Pass i (not i + 1) to the recursive call to allow re-using the element candidates[i].
2. Early Pruning (break): Because the array is sorted in ascending order, if candidates[i] > target, then **all subsequent elements will also be strictly greater than target**. We can immediately break out of the loop and skip the entire subtree.

candidates = [2, 3, 6, 7], target = 7
 
                 target = 7
           /         |         \        \
        pick 2    pick 3     pick 6    pick 7
        (rem 5)   (rem 4)    (rem 1)   (rem 0) -> VALID [7]
       /   |   \
   pick 2 ...
 

import java.util.*;
 
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // Step 1: Sort to enable early pruning
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), result);
        return result;
    }
 
    private void backtrack(int[] candidates, int start, int target, List<Integer> current, List<List<Integer>> result) {
        // Base Case: Match found
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
 
        for (int i = start; i < candidates.length; i++) {
            // Early Pruning: Since candidates is sorted, if candidates[i] > target,
            // no larger element can form a valid sum either.
            if (candidates[i] > target) {
                break;
            }
 
            current.add(candidates[i]);
            // Pass 'i' (not i + 1) to allow reusing the current number
            backtrack(candidates, i, target - candidates[i], current, result);
            current.remove(current.size() - 1); // Backtrack
        }
    }
}
 

Complexity

• Time Complexity: $O(N^{\frac{T}{M}+1})$, where $N$ is candidates.length, $T$ is target, and $M$ is the minimum element in candidates. Sorting takes $O(N\log N)$, and pruning eliminates dead branches early.
• Space Complexity: $O(\frac{T}{M})$ auxiliary space for the recursion call stack.

---

Easy Memory Rule

“For Combination Sum, pass i to keep reusing elements. Sort first, and if candidates[i] > target, break.”