---
title: "#39 Combination Sum"
tags: LeetCode, Top100
---
#39 Combination Sum
==
題目描述
--
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.

It is **guaranteed** 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.

解題思維
--
利用遞迴的性質，找出可能的組合，也不會有重複的可能。

Compare
--

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

        result = []

        def getAnswer(i, target, out):
            if target < 0:
                return
            elif i >= len(candidates) and target > 0:
                return
            elif target == 0:
                result.append(out)
                return

            getAnswer(i, target-candidates[i], out+[candidates[i]])
            getAnswer(i+1, target, out)

        getAnswer(0, target, [])
        return result