Combination Sum

by a guest

Solution for the Combination Sum problem on Leetcode.

Combination Sum

1class Solution:
2    def combinationSum(self, can: List[int], target: int) -> List[List[int]]:
3        res=[]
4        def backtracking(curr: List[int],i:int):
5            s=sum(curr)
6            if s==target:
7                res.append(curr)
8            elif s<target:
9                for j in range(i,len(can)):
10                    backtracking(curr+[can[j]],j)
11        backtracking([],0)
12        return res

✨ Code Explanation ✨

This code implements the backtracking algorithm to find all possible combinations of numbers from a given list that sum up to a target number. The function `combinationSum` takes in two parameters: a list of integers (`can`) and the target sum (`target`). It returns a list of lists, where each inner list contains a combination of integers from the `can` list that add up to the given `target` sum. The `backtracking` function is a recursive helper function that takes in two parameters: `curr`, which is a list of integers that represents the current combination being explored, and `i`, which is the index of the next element to be added to the combination. The function starts by checking if the sum of integers in `curr` is equal to the target sum. If so, it appends `curr` to the result list (`res`). If the sum is less than the target, the function enters a loop that starts from the current index `i` and explores all possible combinations by adding each subsequent element from the `can` list to `curr` and calling the `backtracking` function recursively with the updated `curr` and `i` values. At the end, the `backtracking` function is called with an empty list (`[]`) as the initial combination and the starting index (`0`) of the `can` list. The final result list is returned.