main.py

# Source: https://leetcode.com/problems/combination-sum
# Title: Combination Sum
# Difficulty: Medium
# Author: Mu Yang <http://muyang.pro>

################################################################################################################################
# Given an array of **distinct** integers `candidates` and a target integer `target`, return a list of all **unique combinations** of `candidates` where the chosen numbers sum to `target`. You may return the combinations in **any order**.
#
# The **same** number may be chosen from `candidates` an **unlimited number of times**. Two combinations are unique if the **frequency** of at least one of the chosen numbers is different.
#
# The **frequency** of an element x is the number of times it occurs in the array.
#
# The test cases are generated such that the number of unique combinations that sum up to `target` is less than `150` combinations for the given input.
#
# **Example 1:**
#
# ```
# Input: candidates = [2,3,6,7], target = 7
# Output: [[2,2,3],[7]]
# Explanation:
# 2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
# 7 is a candidate, and 7 = 7.
# These are the only two combinations.
# ```
#
# **Example 2:**
#
# ```
# Input: candidates = [2,3,5], target = 8
# Output: [[2,2,2,2],[2,3,3],[3,5]]
# ```
#
# **Example 3:**
#
# ```
# Input: candidates = [2], target = 1
# Output: []
# ```
#
# **Constraints:**
#
# - `1 <= candidates.length <= 30`
# - `2 <= candidates[i] <= 40`
# - All elements of `candidates` are **distinct**.
# - `1 <= target <= 40`
#
################################################################################################################################

from typing import List


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

        ans = []

        def dfs(candidates: list[int], target: int, *slice: int):
            nonlocal ans
            if target == 0:
                ans.append(list(slice))
                return
            if target < 0:
                return
            if not candidates:
                return

            num = candidates[0]
            nextSlice = list(slice)
            while target >= 0:
                dfs(candidates[1:], target, *nextSlice)
                nextSlice.append(num)
                target -= num

        dfs(candidates, target)

        return ans