39-combination-sum.md

39. Combination Sum - 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。 

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

---

题目标签：Array / Backtracking

题目链接：LeetCode / LeetCode中国

题解

本题难点主要在于组合不重复性。第一次AC使用了非常tricky的做法，使用Python，先用set存储tuple，在返回时把tuple和set再转为list，不过，运行时间较长。

Language	Runtime	Memory
python3	376 ms	N/A

class Solution:
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = set()
        for num in candidates:
            if num == target:
                res.add((num,))
            elif num < target:
                for rst in self.combinationSum(candidates, target - num):
                    res.add(tuple(sorted([num, *rst])))
        return list(map(list, res))