Combination Sum III

class Solution {
public:
    void explore(int left, int count, vector<int>& path, int start,
                 vector<vector<int>>& outputs) {
        if (left == 0 && path.size() == count) {
            outputs.push_back(path);
            return;
        } else if (left < 0 || path.size() == count) {
            return;
        }
    
        for (int j = start; j < 9; ++j) {
            path.push_back(j + 1);
            this->explore(left - j - 1, count, path, j + 1, outputs);
            path.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum3(int count, int target) {
        vector<vector<int>> outputs;
        vector<int> path;
    
        this->explore(target, count, path, 0, outputs);
        return outputs;
    }
};

The "Combination Sum III" problem seeks combinations that add up to a specific target using a specific count of numbers between 1 and 9. Each combination must use only unique numbers. The implementation provided achieves this by using a depth-first search (DFS) approach:

• The combinationSum3 function initializes the path and final outputs and starts the DFS exploration via the explore function.

• The explore function accepts parameters for the remaining sum (left), remaining number count (count), the current combination path (path), current number to consider (start), and the final list of valid combinations (outputs).

• In each recursive call:

  • Check the base condition where if left equals 0 and the path length matches the count, add the path to outputs.
  • If left goes negative or the desired count is reached, the function returns without adding to outputs.
  • Iterate from the start number to 9, adding each number to the current path, then recursively calling explore with updated left, increased path elements, and next number.

• Each number from 1 to 9 is tried once per recursion depth, ensuring unique sets and avoiding combinations of the same elements but in different orders.

This approach ensures efficient exploration of all possible combinations that meet the conditions imposed by the problem, and outputs all valid combinations by recursively building them and uniformly exploring potential candidate numbers.

class Solution {
    protected void searchCombinations(
        int remainingSum,
        int combinationSize,
        LinkedList<Integer> currentCombination,
        int startNum,
        List<List<Integer>> allCombinations
    ) {
        if (remainingSum == 0 && currentCombination.size() == combinationSize) {
            allCombinations.add(new ArrayList<Integer>(currentCombination));
            return;
        } else if (remainingSum < 0 || currentCombination.size() == combinationSize) {
            return;
        }
    
        for (int num = startNum; num < 9; ++num) {
            currentCombination.add(num + 1);
            this.searchCombinations(remainingSum - num - 1, combinationSize, currentCombination, num + 1, allCombinations);
            currentCombination.removeLast();
        }
    }
    
    public List<List<Integer>> combinationSum3(int combinationSize, int targetSum) {
        List<List<Integer>> allCombinations = new ArrayList<List<Integer>>();
        LinkedList<Integer> comb = new LinkedList<Integer>();
    
        this.searchCombinations(targetSum, combinationSize, comb, 0, allCombinations);
        return allCombinations;
    }
}

The Java solution provided outlines a method for finding all unique combinations of numbers that sum up to a given target sum, where each number can only be used once, and the combination must be exactly of a specified size. The solution uses recursion to explore possible combinations, leveraging backtracking to build up potential valid combinations and backtrack once an invalid path is confirmed.

Here's a summary of how the solution operates:

• The core functionality is encapsulated in the searchCombinations method, which recursively attempts to construct valid combinations that meet the criteria.
• The method takes:
  • remainingSum: the sum left to reach the target.
  • combinationSize: the size of each combination to be constructed.
  • currentCombination: the current combination being constructed.
  • startNum: the current number to start from in the recursive search.
  • allCombinations: container to hold all the valid found combinations.
• Recursion is tailormade for this scenario:
  • If remainingSum equals zero and currentCombination's size equals combinationSize, the current combination is added to the allCombinations list, as it indicates a valid combination has been found.
  • If remainingSum drops below zero, or currentCombination's size exceeds combinationSize, it backtracks, avoiding invalid combinations.
• It iteratively explores numbers from startNum to 8 (num = startNum to < 9), representing choices from 1 through 9 (as num + 1). For each number, it's added to the currentCombination, and searchCombinations is called with a decremented remainingSum.
• Post recursive call, it removes the last element added to revert to previous state (backtracking) and continues with the next number.

The combinationSum3 public method initializes parameters and kicks off the recursive search. It initializes:

• allCombinations: to store valid combinations found.
• comb: a LinkedList used to store the current combination.

This method configures the initial state and calls searchCombinations, passing the initial configuration along with fresh parameters, starting from 0 to attempt to build lists up to the targetSum.

The solution leans heavily on recursion and backtracking to explore all potential number combinations, ensuring efficient exploration of possibilities while adhering to the constraint of unique combinations of a fixed size.

class Solution:
    def findCombinationSums(self, count: int, target: int) -> List[List[int]]:
        combinations = []
    
        def searchCombinations(remainder, combination, start):
            if remainder == 0 and len(combination) == count:
                combinations.append(list(combination))
                return
            if remainder < 0 or len(combination) == count:
                return
    
            for num in range(start, 9):
                combination.append(num + 1)
                searchCombinations(remainder - num - 1, combination, num + 1)
                combination.pop()
    
        searchCombinations(target, [], 0)
        return combinations

The given Python solution aims to solve the problem of finding all unique combinations that sum up to a target number (target), using exactly (count) numbers where each number can be used once from values 1 through 9. It defines a class, Solution, with a method findCombinationSums that initializes an empty list, combinations, to store the valid combinations.

Here's an outline of how the method works:

• Start by defining an inner function searchCombinations(remainder, combination, start) to perform recursive searches. The parameters are:

  • remainder - the remaining sum needed to reach the target.
  • combination - the current list of numbers contributing to the sum.
  • start - the starting index for the next iteration to ensure numbers are not reused.

• The base case checks if remainder is zero and the combination length equals the count. If true, it implies a valid combination that adds up to the target using the desired count of numbers, and adds a copy of this combination to the combinations list.

• If the remainder is negative or the length of combination exceeds count, the function returns as these conditions signify invalid combinations.

• A loop iterates from start to 8 (inclusive), representing the digits 1 through 9 respectively. The function attempts to include the next number into the current combination, performs a recursive call adjusting the remainder and start accordingly, then backtracks by removing the last added number from combination.

• The main function call to searchCombinations initiates the process with the full target, an empty list for combinations, and 0 as the initial start value.

• Finally, the method returns the list of valid combinations.

Overall, the approach leverages backtracking to explore all possible number combinations, ensuring no repetitions and adherence to the constraints of using only numbers between 1 and 9.