Python描述 LeetCode 40. 組合總和 II

  大家好，我是亓官劼（qí guān jié ），在【亓官劼】公衆号、GitHub、B站等平台分享一些技術博文，主要包括前端開發、python後端開發、小程式開發、資料結構與算法、docker、Linux常用運維、NLP等相關技術博文，時光荏苒，未來可期，加油~

  如果喜歡部落客的文章可以關注部落客的個人公衆号【亓官劼】(qí guān jié)，裡面的文章更全更新更快。如果有需要找部落客的話可以在公衆号背景留言，我會盡快回複消息.

本文原創為【亓官劼】（qí guān jié ），請大家支援原創，部分平台一直在惡意盜取部落客的文章！！！ 全部文章請關注微信公衆号【亓官劼】。

題目

給定一個候選人編号的集合 ​

​candidates​

​​ 和一個目标數 ​

​target​

​​ ，找出 ​

​candidates​

​​ 中所有可以使數字和為 ​

​target​

​ 的組合。

​

​candidates​

​ 中的每個數字在每個組合中隻能使用 一次 。

**注意：**解集不能包含重複的組合。

示例 1:

輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]      

示例 2:

輸入: candidates = [2,5,2,1,2], target = 5,
輸出:
[
[1,2,2],
[5]
]      

• ​

  ​1 <= candidates.length <= 100​

  ​
• ​

  ​1 <= candidates[i] <= 50​

  ​
• ​

  ​1 <= target <= 30​

  ​

Python描述

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if target == 0:
            return []
        res = set()
        combine = []
        freq = sorted(collections.Counter(candidates).items())

        def dfs(idx, rest):
            nonlocal combine
            if rest == 0:
                res.add(tuple(combine))
                return
            # 一個也拿不了，直接傳回
            if idx == len(freq) or rest < freq[idx][0]:
                return

            # 跳過，不要這個數
            dfs(idx + 1, rest)

            # 要這個數，可以要1-freq[idx][1]個
            tmp_num = freq[idx][0]
            for i in range(1, freq[idx][1] + 1):
                combine.append(tmp_num)
                dfs(idx + 1, rest - tmp_num*i)
            combine = combine[:-freq[idx][1]]
        dfs(0, target)
        return [_ for _ in res]