# Java recursive solution with explanatory comments/example

• This solution was heavily inspired by my code from Combination Sum: https://leetcode.com/discuss/98311/java-recursive-solution-with-explanatory-comments-example

Please see the code comments for explanations and an example worked out for the recursive case.
__

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

// Degenerate case: candidates is empty.
// We have no candidates to form a combination.
if (candidates.length == 0) {
}

// 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) {

// 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) {
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] equals target.
if (numCandidates == 1) {
if (target == candidates[0]) {
}
return combos;
}

// Recursive Case
// Example:
//    Given C = {2,3,3,6,7} and T = 8.
// Strategy:
//      First get all combos containing one 7,
//      then get all combos containing one 6 but no 7,
//      then get all combos containing one 3 but no 6 or 7,
//      then get all combos containing two 3s 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 - {7}, T - 7) = S({2,3,3,6}, 1)         (we append a 7 to the end of these sub-combos)
//      S(C - {6,7}, T - 6) = S({2,3,3}, 2)     (we append a 6 to the end of these sub-combos)
//      S(C - {3,3,6,7}, T - 3) = S({2,3}, 5)     (we append one 3 to the end of these sub-combos)
//      S(C - {3,3,6,7}, T - 2*3) = S({2}, 2)     (we append two 3s to the end of these sub-combos)
//      S(C - {2,3,3,6,7}, T - 2) = S({}, 6)     (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.
int runLength = 0;
for (int i = numCandidates - 1; i >= 0; i--) {
runLength++;
if (i == 0 || candidates[i - 1] < candidates[i]) {
// we've found the left end of a run of a value
for (int j = 0; j < runLength; j++) {
List<List<Integer>> subCombos = getCombinations(candidates, i, target - candidates[i] * (j + 1));
for (List<Integer> subCombo : subCombos) {
for (int k = 0; k < (j + 1); k++) {
}