Problem Statement: The combination sum problem on LeetCode is a problem that requires us to find all the combinations of numbers from an input array that sum up to a target number.

Example:

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]]

Solution:

The solution to this problem can be found using recursion and backtracking. The basic idea is to try all possible combinations of the input array to check if any combination sums up to the target number. The steps involved in solving this problem are:

Step 1: Sort the input array in ascending order to ensure that we generate combinations in a specific order.

Step 2: Define a recursive function that takes the following parameters - candidates array, target, a current index to keep track of the index in the array we are currently at, a path to store the current path we are on while traversing the recursive tree, and a result list to store the valid combinations that sum up to the target.

Step 3: Inside the recursive function, check if the current sum of all the elements in the path equals the target. If yes, append the path to the result list.

Step 4: Loop through the sorted input array starting from the current index, and for each element, append it to the path and call the recursive function with the updated path and target minus the current element.

Step 5: After the recursive call, remove the last element from the path to backtrack and try the next possible combination.

Step 6: Once all possible combinations have been tried, return the result list containing all valid combinations.

Code:

def combinationSum(candidates, target): candidates.sort() result = []

def backtrack(current_sum, index, path):
    if(current_sum==target):
        result.append(path)
    
    for i in range(index, len(candidates)):
        if(current_sum + candidates[i] > target):
            break
        backtrack(current_sum + candidates[i], i, path + [candidates[i]])

backtrack(0, 0, [])
return result

Example Usage

candidates = [2,3,6,7] target = 7 print(combinationSum(candidates, target))

Output: [[2, 2, 3], [7]]

1