# Combination sum problem

Given an array of integers (`candidates`) (without duplicates) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sums to `target`.

Also, same candidate can occur in the combination as multiple times.

For example, Input: candidates = [4,3,5,9], target = 9, a solution set is:[ , [3,3,3], [4,5]]

How can do we go about it? What happens if I take the coin 4 in the current example? Then all need to find in the `candidates` array if there is a combination adds up to 9-4 = 5. Seems like a recursion. For recursion, we need a termination condition. In this case, if I have on candidates to add and `target` is greater than zero, then whatever combination I have till now has no value, so I terminate the recursion in this case.

Second what if I have already found a combination which adds up to `target`? Then I will put that combination in the list of combinations and return.

What happens in recursive implementation? Well, we go through each coin, add that to current combination and see if leads to the target? If it does, it will be added to the result list along with the list of other candidates. If not, we just remove the current coin (backtrack) from the current combination and try the next coin.

This approach is called exhaustive search and backtracking paradigm of problem-solving where you search the entire input set to see to find the answer. However, in this case, we can prune the search path as soon as we know that the current set of candidates add up more than the target.

## Combination sum : implementation

```class Solution {
public List<List<Integer>> combinationSum(int[] candidates,
int target) {
/* The result list contains all the combination
which add up to target.
*/
List<List<Integer>> result = new ArrayList<List<Integer>> ();

//We start with the first coin and search exhaustively.
combinationSumUtil(candidates,
target,
result,
new ArrayList<Integer>(),
0
);

return result;

}

public void combinationSumUtil(int[] candidates,
int target,
List<List<Integer>> result,
List<Integer> current,
int index){

/*
First termination condition: if there are no coins left
and required target is more than zero.
*/
if(target > 0 && index == candidates.length){
return;
}

/*
Second termination condition: if target is zero,
we can add the current combination to the result
*/
if(target == 0 && index < candidates.length){
result.add(new ArrayList<>(current));
return;
}

/*
Start from the current index, and go through
all the coins.
*/
for(int i=index; i<candidates.length; i++){
/*
This is where we prune the branches
of our exhaustive search
*/
if(target - candidates[i] >=0){
current.add(candidates[i]); // add to the list
combinationSumUtil(candidates,
target-candidates[i],
result, current, i);

/* Remove the candidate from the list and
check other combinations.
*/
if(current.size() > 0)
current.remove(current.size()-1);
}
}

}
}
```

The time complexity is C(n,1) + C(n,2) + … + C(n,n) = 2^n – C(n,0) = `O(2n)`.

The beauty of this solution is that it works with negative candidates as well, where the Dynamic solution for it may not work.