# LeetCode 39. Combination Sum

## Description

https://leetcode.com/problems/combination-sum/description/

Given a set of candidate numbers (C(without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set `[2, 3, 6, 7]` and target `7`,
A solution set is:

```[
[7],
[2, 2, 3]
]```

## Explanation

Combinations are similar to subsets of the candidate array. We can use depth-first search to find all combinations of the input array.

First, sort candidates array into ascending order.
Second, conduct a depth-first search to visit each combination of the input array.

A depth-first search function would be:
Whenever adding an element to the combination, we reduce the target.
If the remaining target value is equal to 0, we add the current combination to the result list.
Then, recursively find all combinations for the remaining target value from the remaining elements.

## Java Solution

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

if (candidates == null || candidates.length == 0) {
return results;
}

Arrays.sort(candidates);

List<Integer> combination = new ArrayList<>();
toFindCombinationsToTarget(results, combination, candidates, target, 0);

return results;
}

private void toFindCombinationsToTarget(List<List<Integer>> results, List<Integer> combination, int[] candidates, int target, int startIndex) {
if (target == 0) {
return;
}

for (int i = startIndex; i < candidates.length; i++) {
if (candidates[i] > target) {
break;
}

toFindCombinationsToTarget(results, combination, candidates, target - candidates[i], i);
combination.remove(combination.size() - 1);
}
}
}```

## 4 Thoughts to “LeetCode 39. Combination Sum”

1. Yamato says:

Hey GoodTecher! Thank you so much for the tutorials! They are awesome. Can you please do more DP problems, showing how to think and attack those problems?
Also, please do Combination Sum IV.

1. Thank you Yamato. Will take a look at the question 🙂

2. Em says:

Hi Good Techer,

Thank you so much for making this video in comparison with the previous one. They are very helpful.

Looking forward to your next video.
With all my thanks,

1. GoodTecher says:

Sure! You are welcome!