_39. Combination Sum.md

39. Combination Sum

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 16, 2024

Last updated : July 16, 2024

---

Related Topics : Array, Backtracking

Acceptance Rate : 73.4 %

---

Solutions

• m39.py

Python

m39.py

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

        def combos(outputs: List[List[int]], 
                   current: List[int] = [], 
                   currentSum: int = 0, 
                   candidates: List[int] = candidates) -> None :
            if currentSum > target :
                return
            if currentSum == target :
                outputs.append(current.copy())
                return
            if not candidates :
                return

            hold = candidates.pop()
            combos(outputs, current, currentSum, candidates)
            currentSum += hold
            cnt = 0

            while currentSum <= target :
                current.append(hold)
                cnt += 1
                combos(outputs, current, currentSum, candidates)
                currentSum += hold

            for _ in range(cnt) :
                current.pop()
            candidates.append(hold)

        candidates.sort()
        output = []
        combos(output)

        return output