# Solving Combination Sum

To see the question, click **here**.

**Naive Approach**

The idea is to use the concept of backtracking. Initialize a result list to store all valid combinations and a temporary list `temp`

to store the current combination being explored. Assume a recursive function `f`

is called to generate combinations recursively. This function takes several parameters: the current index `i`

, the input array `candidates`

, the target sum, the result list `result`

, the temporary list `temp`

, the current sum `currSum`

, and the length of the `candidates`

array `n`

. The function then explores two possibilities at each step, including the current element `candidates[i]`

in the combination or excluding it. When the element is included, it is added to `temp`

, and `currSum`

is updated accordingly. The function is called recursively with the same index `i`

to allow repeated use of the same element. When the element is excluded, it is removed from `temp`

, and `currSum`

is decremented accordingly. The function is called recursively with the next index `i + 1`

to explore the next element. This approach ensures that every possible combination that sums to the target is generated by exploring each element's inclusion or exclusion. Backtracking is used to remove the last added element from `temp`

before exploring the exclusion path, ensuring all combinations are considered. This method guarantees that all valid combinations are efficiently generated and stored in the result list. The base case of the recursion occurs when the index `i`

equals `n`

or the `currSum`

exceeds the target.

```
// TC: O(2^n)
// SC: O(n)
import java.util.List;
import java.util.ArrayList;
class CombinationSum {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
int n = candidates.length;
f(0, candidates, target, result, temp, 0, n);
return result;
}
public void f(int i, int[] candidates, int target, List<List<Integer>> result, List<Integer> temp, int currSum,
int n) {
if (i == n || currSum > target) {
return;
}
if (currSum == target) {
result.add(new ArrayList<>(temp));
return;
}
// include
currSum += candidates[i];
temp.add(candidates[i]);
f(i, candidates, target, result, temp, currSum, n);
// exclude
currSum -= candidates[i];
temp.remove(temp.size() - 1);
f(i + 1, candidates, target, result, temp, currSum, n);
}
public static void main(String args[]) {
CombinationSum cs = new CombinationSum();
int[] candidates = { 2, 3, 6, 7 };
int target = 7;
System.out.println(cs.combinationSum(candidates, target));
}
}
```

**Performance**

The time complexity of the `combinationSum`

method is O(2^n) because we have two choices for each element in the candidate's array: either include it in the combination or exclude it. This results in a binary tree of height n. As a result, the total number of combinations that can be formed is 2^n. The space complexity is O(n) because we are using a temporary list to store the current combination, and the maximum size of this list is equal to the number of elements in the array.

**Refined Approach**

Start by sorting the array. This allows us to break early from the recursion when the current sum exceeds the target, as all further elements will only make the sum larger. Instead of passing `currSum`

around, we can calculate the sum directly in the recursive call by including or excluding the current candidate. It's important to note that the fundamental time complexity might not drastically change due to the nature of the problem.

```
// TC: O(2^n)
// SC: O(n)
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
public class CombinationSum {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates);
f(candidates, target, result, new ArrayList<>(), 0);
return result;
}
public void f(int[] candidates, int target, List<List<Integer>> result, List<Integer> temp, int start) {
if (target == 0) {
result.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < candidates.length && target >= candidates[i]; i++) {
temp.add(candidates[i]);
f(candidates, target - candidates[i], result, temp, i); // not i + 1 because we can reuse same elements
temp.remove(temp.size() - 1); // remove the last element for backtracking
}
}
public static void main(String[] args) {
CombinationSum solution = new CombinationSum();
int[] candidates = {2, 3, 6, 7};
int target = 7;
List<List<Integer>> result = solution.combinationSum(candidates, target);
System.out.println(result);
}
}
```

**Performance**

The time complexity of the `combinationSum`

method is O(2^n) because we have two choices for each element in the candidate's array: either include it in the combination or exclude it. This results in a binary tree of height n. As a result, the total number of combinations that can be formed is 2^n. The space complexity is O(n) because the recursion stack can reach a depth of n as we explore all possible combinations of elements in the array. While the worst-case time complexity remains exponential due to the nature of the problem, these optimizations can significantly improve performance in practice by reducing the number of paths explored.

Thank you for reading!

Check out other DSA patterns **here**.

You can support me by **buying me a book****.**