Combination Sum

class Solution {
public:
    void searchCombos(int target, vector<int>& current, int startIdx,
                      const vector<int>& numbers,
                      vector<vector<int>>& allCombos) {
        if (target == 0) {
            allCombos.push_back(current);
            return;
        } else if (target < 0) {
            return;
        }

        for (int i = startIdx; i < numbers.size(); ++i) {
            current.push_back(numbers[i]);
            searchCombos(target - numbers[i], current,
                         i,  // keep i to allow duplicates
                         numbers, allCombos);
            current.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int goal) {
        vector<vector<int>> allCombos;
        vector<int> tempCombo;

        searchCombos(goal, tempCombo, 0, candidates, allCombos);
        return allCombos;
    }
};

The provided C++ solution defines a method to find all possible combinations of numbers from a given set (candidates) that sum up to a specified goal. Below is the method for how this solution is structured:

• The combinationSum function initializes the process. It prepares a temporary storage (tempCombo) for current combinations and a container (allCombos) to hold all valid combinations. The searchCombos function is then called with the initial conditions.

• The searchCombos function is a recursive method designed to explore each potential combination. It takes the current summing target, the ongoing combination of numbers, the starting index in candidates, the list of candidate numbers, and the storage for valid combinations.

• Inside searchCombos, the function first checks if the target is zero, indicating that the current combination sums up to the goal, hence added to allCombos. If the target becomes negative, the function returns immediately as further additions will only increase the negative deficit.

• The core of the method relies on a loop starting from startIdx through each number in the candidates list. For each number, it's added to the current combination, and the function is recursively called with an adjusted target (target - numbers[i]). This allows continuous addition of the same number or exploration of subsequent numbers, serving combinations where numbers can repeat.

• After each recursive call, the last number added to the combination is removed (current.pop_back()), ensuring backtracking and exploration of new combinations upon returning from recursion.

In summary, this approach ensures all combinations are explored by systematically adding numbers to a working combination, recursively adjusting the target, and backtracking to explore alternate paths.

class Solution {
    protected void findCombinations(
        int remaining,
        LinkedList<Integer> currentCombination,
        int startIndex,
        int[] options,
        List<List<Integer>> allCombinations
    ) {
        if (remaining == 0) {
            allCombinations.add(new ArrayList<Integer>(currentCombination));
            return;
        } else if (remaining < 0) {
            return;
        }

        for (int i = startIndex; i < options.length; ++i) {
            currentCombination.add(options[i]);
            this.findCombinations(
                    remaining - options[i],
                    currentCombination,
                    i,
                    options,
                    allCombinations
                );
            currentCombination.removeLast();
        }
    }

    public List<List<Integer>> getCombinationSum(int[] options, int goal) {
        List<List<Integer>> allCombinations = new ArrayList<List<Integer>>();
        LinkedList<Integer> currentCombination = new LinkedList<Integer>();

        this.findCombinations(goal, currentCombination, 0, options, allCombinations);
        return allCombinations;
    }
}

The Java code provided defines a solution for generating all possible combinations of numbers from a given array that sum up to a specific target value. Here's how the solution operates:

• The Solution class contains two main methods: findCombinations and getCombinationSum.
• getCombinationSum(int[] options, int goal) is the public method designed to be called with the array of numbers (options) and the target sum (goal). This method initializes structures for storing combinations and triggers the recursive search.
• findCombinations(int remaining, LinkedList<Integer> currentCombination, int startIndex, int[] options, List<List<Integer>> allCombinations) is a recursive method tasked with identifying valid combinations:
  • It accepts the remaining sum to fulfill (remaining), the current combination of numbers (currentCombination), the starting index for options (startIndex), the array of potential numbers to use (options), and a list to store all valid combinations found (allCombinations).
  • If the remaining sum is zero, the current combination is a valid solution and is added to allCombinations.
  • If the remaining sum becomes negative, the present path is abandoned as no further valid sum can be achieved with additional positive integers.
  • The recursion occurs within a loop that begins at the startIndex to ensure numbers can be reused and combinations are built incrementally. After exploring adding an option to the combination, it removes the last added element to backtrack and explore other possibilities.

This approach ensures all combinations that sum up to the target are found, supporting multiple uses of the same number. The use of a linked list for the current combination assists in efficiently adding and removing elements during the search process.

void search_combinations(int remaining, int *current_comb, int size_of_comb, int idx, int *elements,
                          int elements_count, int ***solutions, int *count_of_results,
                          int **result_lengths) {
    if (remaining == 0) {
        int *solution = (int *)malloc(size_of_comb * sizeof(int));
        for (int j = 0; j < size_of_comb; j++) {
            solution[j] = current_comb[j];
        }
        (*result_lengths)[*count_of_results] = size_of_comb;
        (*solutions)[*count_of_results] = solution;
        (*count_of_results)++;
        return;
    } else if (remaining < 0) {
        return;
    }

    for (int j = idx; j < elements_count; j++) {
        current_comb[size_of_comb] = elements[j];
        search_combinations(remaining - elements[j], current_comb, size_of_comb + 1, j, elements,
                            elements_count, solutions, count_of_results, result_lengths);
    }
}

int **find_combinations(int *elements, int count, int target_sum,
                        int *number_of_results, int **sizes_of_results) {
    int max_possibilities = 1000;
    int **combinations = (int **)malloc(max_possibilities * sizeof(int *));
    *sizes_of_results = (int *)malloc(max_possibilities * sizeof(int));
    *number_of_results = 0;

    int *partial = (int *)malloc(target_sum * sizeof(int));

    search_combinations(target_sum, partial, 0, 0, elements, count, &combinations,
                        number_of_results, sizes_of_results);

    free(partial);
    return combinations;
}

The provided C code implements a solution to the Combination Sum problem, where the aim is to find all unique combinations of elements that sum up to a given target number. The implementation primarily involves two recursive functions: search_combinations and find_combinations.

• The search_combinations function recurses through the input array elements to build up potential combinations in the current_comb array. This function uses two key base cases:

  • When the remaining sum (remaining) needed to reach the target amount is zero, a valid combination is found and added to the solution set.
  • If the remaining sum becomes negative, the current path is abandoned as adding more numbers will only stray further from the target.

• search_combinations allows for repetition of elements in the combination by not incrementing the index when making the recursive call if a valid element is used.

• The find_combinations function sets up the necessary variables for recursion, including dynamically allocated arrays for storing combinations and their sizes. It begins the recursion and handles the cleanup of temporary storage.

• Proper memory management is demonstrated:

  • Memory for potential combinations and their sizes is allocated before the recursion begins and dynamically managed during recursion.
  • Temporary arrays are freed after their use to prevent memory leaks.

This arrangement ensures that all possible combinations that sum up to the target are explored and stored efficiently using dynamic memory management. The implementation maximizes recursion for exhaustive search while maintaining control over memory and avoiding unnecessary computations. This is a classic example of applying combinatorial generation with backtracking in C programming.

var findCombinations = function (nums, sum) {
    function solve(remaining, idx, current) {
        if (remaining < 0) {
            return;
        }
        if (remaining === 0) {
            result.push([...current]);
            return;
        }
        for (let i = idx; i < nums.length; i++) {
            current.push(nums[i]);
            solve(remaining - nums[i], i, current);
            current.pop();
        }
    }
    const result = [];
    solve(sum, 0, []);
    return result;
};

This solution addresses the problem of finding all unique combinations of elements in an array that sum up to a specified target value. The given code is written in JavaScript and employs a recursive backtracking approach to solve this problem. Given a list of candidate numbers (nums) and a target sum (sum), the function findCombinations looks for all possible ways to generate this sum using the elements of the array where each number can be used multiple times in the combinations.

Here's a breakdown of how this approach works:

• Define the outer function findCombinations which initiates the process by calling a helper function solve.
• The solve function executes recursively, and it maintains the current state of the combination it's building using current array.
• It takes three arguments:
  • remaining: the remaining sum to fulfill the target.
  • idx: the current starting index in nums to avoid re-using elements which are situated before this index in the array.
  • current: the current combination of numbers that is being tested.
• If remaining drops below zero, the current combination is abandoned (i.e., the function returns without action).
• If remaining is exactly zero, a valid combination is found, and it's added to the result list.
• Loop through the elements starting from idx to try including each number in the current combination and see if it can form the target sum. Using the same element more than once is allowed as the function calls itself with the same index i.
• After exploring the inclusion of a number, it is removed from the current array (current.pop()) to backtrack and try the next potential number.

The function tracks all successful combinations in the result list, which is initialized in the findCombinations function and returned at the end.

This combination sum problem is a classic example to demonstrate the power of backtracking for solving constraint satisfaction problems and is effectively handled by this recursive approach in JavaScript.

class Solution:
    def findCombinations(
        self, nums: List[int], sum_goal: int
    ) -> List[List[int]]:

        all_combinations = []

        def recurse(current_sum, current_combo, index):
            if current_sum == 0:
                all_combinations.append(list(current_combo))
                return
            elif current_sum < 0:
                return

            for i in range(index, len(nums)):
                current_combo.append(nums[i])
                recurse(current_sum - nums[i], current_combo, i)
                current_combo.pop()

        recurse(sum_goal, [], 0)

        return all_combinations

The given Python code provides a solution to find all unique combinations of numbers that sum up to a specific target. The numbers used in the combinations can be repeated any number of times. The function findCombinations achieves this using recursion.

Here's an overview of the process:

• Begin by defining an inner recursive function recurse, which is utilized to explore each potential combination.
• The base case for recursion is when the current sum equals zero, indicating a valid combination has been found, which is then added to all_combinations.
• If the current sum becomes negative, the function returns as no valid combination can be achieved by proceeding further.
• The recursion proceeds by iterating through the numbers starting from the current index. This preserves the order, preventing duplicates and allowing repeated use of elements.
• For each number, add it to the current combination and recursively call the function with the updated sum.
• Backtrack after the recursive call by removing the last added number to explore the next possibility.

This implementation ensures that all combinations are explored without repetition of combinations, using backtracking efficiently to gather all possible outcomes that match the target sum.