Combination Sum

Dynamic Programming
Medium

Approach

Diagrams

Analysis

Time

Space

class Solution:
    def combinationSum(self, candidates, target):
        def dfs(path, uniqueCombinations, startIdx, currentSum):
            if currentSum == target:
                uniqueCombinations.append(path[:])
                return

            for candidateIdx in range(startIdx, len(candidates)):
                candidateNum = candidates[candidateIdx]
                newSum = currentSum + candidateNum

                if newSum > target:
                    continue

                path.append(candidateNum)
                dfs(path, uniqueCombinations, candidateIdx, newSum)
                path.pop()

        uniqueCombinations = []
        dfs([], uniqueCombinations, 0, 0)
        return uniqueCombinations

Learn

#Backtracking

#Dedup

Videos