Java recursive solution with explanatory comments/example


  • 0
    B

    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;
    }

Log in to reply
 

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