40. 组合总和 II [medium]

https://leetcode-cn.com/problems/combination-sum-ii/

给定一个数组 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]
]

通过次数69,792 | 提交次数112,070

First Try

2020-07-24

其实有点挟0039之威，直接按照类似思路下来就搞定了，不然可能在重复项部分要花费点时间。

依然是回溯递归方法，为了避免出现重复项，对可选项进行排序，每次要么选择当前元素，要么不选择，之后只能选择下一个其他元素。这样的写法可以避免数字选择的重复，也极大的降低了冗余时间。

另外一个问题是相同数字之间的重复，这个就有点尴尬了，按照上一个去重的思路，在这里依然会被重复。比如candidate = [1,1, 6], target = 7，会出现两个[1, 6]的答案。参照0039的思路，相同数字可以汇合成一次选择，在这次选择中，可以选择0到n次该数字，接下来只能移动到下一个数字上。

bingo, 顺利解决。

唯一出现的一个耗时较久的bug，是在遍历重复项 n duplicates * selected的时候，用上了range(duplicates), 但这会导致减少一个选择，需要使用的分明是range(duplicates + 1)。类似这种边角料的低级错误有时候反而是耗时最久的地方。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        # candidates = [1, 1, 6], target = 7的时候，只允许出现[1, 6]，而不是两个[1, 6]
        def combo(arr, start, target, seq, rv):
            if target == 0:  # 需要比后面的判断提前才行
                rv.append(seq[:])
                return 
            if target < 0 or start > len(arr) - 1 or arr[start] > target:
                return 

            end = start 
            while end + 1 <= len(arr) - 1 and arr[end + 1] == arr[end]:
                end += 1
            duplicates = end - start + 1
            for i in reversed(range(duplicates + 1)): # 需要duplicates + 1才行，一个花费了点时间的bug...
                seq.extend([arr[start]] * i)
                # print("inner", i, arr[start], seq, rv)
                combo(arr, start + duplicates, target - i * arr[start], seq, rv)
                for _ in range(i):
                    seq.pop()
                # print("after", i, arr[start], seq, rv)

            # 如果candidates中没有重复，就是下面的写法
            # # 不选择当前元素
            # combo(arr, start + 1, target, seq, rv)
            # # 选择当前元素, 
            # seq.append(arr[start])
            # combo(arr, start + 1, target - arr[start], seq, rv)
            # seq.pop()

        if not len(candidates):
            return []
        candidates = sorted(candidates)
        rv = []
        combo(candidates, 0, target, [], rv)
        return rv 

执行用时：80 ms, 在所有 Python3 提交中击败了43.92%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了14.29%的用户

40. 组合总和 II [medium]​

First Try​

40. 组合总和 II [medium]

First Try