Combination Sum

Combination Sum#

If you want to find all possible unique combinations of a given set of candidate numbers (without duplicates) and a target number, you can use the Combination Sum algorithm. This algorithm can be implemented using backtracking.

Algorithm Steps:#

• Sort the given candidate numbers in ascending order.
• Start with an empty list, and add candidates to the list in a way that the sum of the list is less than or equal to the target number.
• When the sum of the list becomes equal to the target number, add the list to the result set.
• If the sum of the list exceeds the target number, backtrack and remove the last added candidate from the list.

Example:#

def combinationSum(candidates, target):
    candidates.sort()
    result = []
    def backtrack(start, target, path):
        if target == 0:
            result.append(path)
            return
        for i in range(start, len(candidates)):
            if candidates[i] > target:
                break
            backtrack(i, target - candidates[i], path + [candidates[i]])
    backtrack(0, target, [])
    return result

In this example, we are taking a sorted list of candidate numbers and a target number as input. We then initialize an empty list called "result" which will hold all possible unique combinations of numbers whose sum is equal to the target number.

We define a function called "backtrack" that takes three arguments - "start", "target", and "path". "Start" is the index of the first candidate number in the sorted list, "target" is the remaining sum that we need to achieve the target, and "path" is the list of numbers that we have already added to achieve the sum.

In this function, we check if the target is equal to zero. If it is, we append the path (list of numbers) to the result list. If not, we loop through the candidates starting from the "start" index. If a candidate is greater than the target, we break the loop since all subsequent candidates will also be greater than the target. We then call the "backtrack" function recursively by passing the current index as the new "start" index, the remaining target after subtracting the current candidate as the new "target" sum, and the current path appended with the current candidate as the new "path".

We call the "backtrack" function initially by passing 0 as the start index, the target number as the target sum, and an empty list as the initial path.

We return the result list which will contain all possible unique combinations of numbers whose sum is equal to the target number.