# Java recursive solution with explanatory comments/example

• Please see the comments for the recursive case for a worked out example.

``````public List<List<Integer>> combinationSum(int[] candidates, int target) {

// Degenerate case: candidates is empty.
// We have no candidates to form a combination.
if (candidates.length == 0) {
return new LinkedList<>();
}

// IMPORTANT: recursive algorithm relies on the candidates being sorted
Arrays.sort(candidates);
return getCombinations(candidates, candidates.length, target);
}

public List<List<Integer>> getCombinations(int[] candidates, int numCandidates, int target) {

List<List<Integer>> combos = new LinkedList<>();

// Base Case 0: target equals 0
// Because all the candidate numbers are positive, the only combination that sums to 0 is the empty combination.
if (target == 0) {
combos.add(new LinkedList<Integer>());
return combos;
}

// Base Case 1: target is positive, but less than the smallest candidate
// Because the candidates are strictly positive, no combination of them can sum to target.
if (target < candidates[0]) {
return combos;
}

// Base Case 2: candidates has only one item.
// In this case, there is a (single) combo containing only candidates[0] precisely when
// candidates[0] evenly divides target.
if (numCandidates == 1) {
if (target % candidates[0] == 0) {
List<Integer> combo = new LinkedList<>();
int timesRepeated = target / candidates[0];
for (int i = 0; i < timesRepeated; i++) {
combo.add(candidates[0]);
}
combos.add(combo);
}
return combos;
}

// Recursive Case
// Example:
//    Given C = {2,3,6,7} and T = 7.
// Strategy:
//      First get all combos containing a 7,
//      then get all combos containing a 6 but no 7,
//      then get all combos containing a 3 but no 6 or 7,
//      then get all combos containing a 2 but no 3, 6, or 7.
//      Then return all of these combinations.
// Recursive calls are:
//      S(C, T - 7) = S({2,3,6,7}, 0)         (we append a 7 to the end of these sub-combos)
//      S(C - {7}, T - 6) = S({2,3,6}, 1)     (we append a 6 to the end of these sub-combos)
//      S(C - {7,6}, T - 3) = S({2,3}, 4)     (we append a 3 to the end of these sub-combos)
//      S(C - {7,6,3}, T - 2) = S({2}, 5)     (we append a 2 to the end of these sub-combos)
// Notice that all recursive calls either decrease the number of candidates or decrease the size of target,
// so we always reach a base case.
// We use the numCandidates parameter to avoid the need to create a copy
// of a subarray of candidates for each recursive call.
for (int i = numCandidates - 1; i >= 0; i--) {
List<List<Integer>> subCombos = getCombinations(candidates, i + 1, target - candidates[i]);
for (List<Integer> subCombo : subCombos) {
subCombo.add(candidates[i]);
combos.add(subCombo);
}
}

return combos;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.