39. Combination Sum

Medium

Problem:

List all elements from the set of numbers, "candidates", in combinations that sum up to "target". Each element can be listed more than once.

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

https://leetcode.com/problems/combination-sum

Solution:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []

        def addition(elements):
            sum = 0
            if elements:
                for el in elements:
                    sum += el
            return sum
        def dfs(cur):
            if addition(cur) == target:
                # Avoid duplicates
                if sorted(cur[:]) not in results:
                    results.append(sorted(cur[:]))
                return

            for num in candidates:
                if num <= target:
                    if num <= target - addition(cur):
                        cur.append(num)
                        dfs(cur)
                        cur.pop()

        dfs([])
        return results

Better approach

It's a problem of exploring the combination graph with duplicates using DFS (Depth-First Search) and backtracking.

If it were a permutation problem, child nodes would always have to start from the beginning, requiring much more computation. However, for combinations, each node can be organized with listings from itself to its lower elements only.

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []

        def dfs(csum, index, path):
            if csum < 0:
                return
            if csum == 0:
                result.append(path)
                return
            
            for i in range(index, len(candidates)):
                dfs(csum - candidates[i], i, path + [candidates[i]])

        dfs(target, 0, [])
        return result