LeetCode——组合总和II（Combination Sum II）

﹏ヽ暗。殇╰゛Y 2022-05-14 04:40 184阅读 0赞

# **题目**： #

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

`candidates` 中的每个数字在每个组合中只能使用一次。

**说明：**

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

**示例 1:**

输入: candidates = [10,1,2,7,6,1,5], target = 8,
    所求解集为:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]

**示例 2:**

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

# **思路**： #

这题看起来跟上一题差不多，所以这里我们需要列出与上一题不同之处，这样方便解题：

*  list中的每个数只能取一次，不能去无数次了
 *  list中不像上一题排好序，这里特别说明以后看到无序的数组，请先排序，有助于你更好的想到思路
 *  返回的结果集必须是无重复的。

看完不同之处，这里讲下思路，有些同学可能排完序之后，就想到这题只要将有放回取变成无放回去不就可以了，然后再在返回结果集的时候去重一下不就完事了，这样做没有问题，但是在提交的时候，会提示超时，为什么会超时的，就是因为在上一题中同一个数字，我们只有一个分支，而这里可能会有多个重复分支，造成浪费。如图所示：

![70][]

从上面可以看出，如果要得到结果之一\[1,2,2\],上一题中，我们只要最左边的分支就可以了，但是在这道题中，我们需要重复3次，这就是为什么超时的原因。如果解决呢？这里就要转化思想，有限重复数字的有放回取和无重复数字的无限放回取差别在哪呢？答案就是数字的个数，我们只要限制数字的个数，就可以跟套用上一题的代码，保证一个结果集只用一个分支。

# **代码**： #

class Solution:
        def combinationSum2(self, candidates, target):
            """
            :type candidates: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            self.result = []#存放结果集
            self.cnt = [0 for i in range(len(set(candidates)))]#存放每个数在list中数量
            self.target1 = target
            i = 0
            #下面进行排序，使用的是最容易想到的选择排序
            while i < len(candidates) - 1:
                j = i+1
                while j < len(candidates):
                    if candidates[i] > candidates[j]:
                        candidates[i], candidates[j] = candidates[j], candidates[i]
                    j += 1
                i += 1
            #K是cnt的index
            k = 0
            candidates_copy = []#因为这里遍历了一遍有序的candidates，所以这里去重，并保证数据的有序性
            for index , num in enumerate(candidates):
                if index == 0:#第一个数
                    self.cnt[k] = 1
                    candidates_copy.append(num)
                elif num == candidates[index - 1]:#如果连续相等的数，则记录个数
                    self.cnt[k] += 1
                else:#不想等，则统计新的数字的个数
                    k += 1
                    self.cnt[k] = 1
                    candidates_copy.append(num)
            for index, num in enumerate(candidates_copy):
                temp = []  # 保存一次计算的结果
                temp.append(num)
                cnt1 = copy.deepcopy(self.cnt)#这里之所以这么做，是因为cnt是原始数据，不能被改动，但是list在python中是可改变对象，就是函数体内的改变会影响外面
                cnt1[index] -= 1#因为前面已经添加了，所以这里需要对数量减一
                self.helper(candidates_copy, index, temp, cnt1)#下面的递归跟组合求和1是差不多的。
            return self.result
        def helper(self,candidates,index,temp, cnt):
            temp1 = copy.deepcopy(temp)
            if sum(temp1) == self.target1:
                # if temp1 not in self.result:
                self.result.append(temp1)
                return
            elif sum(temp1) < self.target1:
                for i, num in enumerate(candidates[index:]):
                    if cnt[index+i] > 0:#只有剩余数额大于0，才能添加
                        temp1.append(num)
                        cnt[index + i] -= 1 #上面添加了，所以这需要减一
                        self.helper(candidates, index+i, temp1,cnt)
                        temp1.pop()
                        cnt[index+i] +=1
            elif sum(temp1) > self.target1:
                 return
    if __name__ =="__main__":
        res = Solution()
        print(res.combinationSum2([10,1,2,7,6,1,5], 8))
        pass

[70]: /images/20220514/5fb01607e6a944be9ab8b0eb2550a02e.png