40.md

题目地址

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

解答1

class Solution:
    def __init__(self):
        self.res = []

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        """
            组合总和, 不重复使用元素

            递归回溯，同时要去重。
            为啥能通过比较相同然后移动扫描下标就能去重？
            假设[i, j]区间中要找一个和为M。
            而如果[i+1, j]区间有好几个值跟v[i]相等，但是此区间==v[i]元素的个数一定比v[i, j]区间==v[i]元素的个数少；
            所以对于"含有v[i]的解"中，前者的答案一定包含后者，所以我们只需要求一次就行；
            后面相同的元素直接跳过去。

            图示：假设这个相同的数为3

            3 [3......3333.....3(第k个3)]4673435....
            i i+1                                   j

            既然区间[i+1, j]能够求出和为M的组合，其中包含了所有3的情况。
            而区间[i, j]3的个数比[i+1, j]3的个数更多，那么毫无疑问，[i, j]的解将覆盖[i+1, j]解中含有3的情况。
        """
        candidates.sort()  # 先排序
        self.getResult(candidates, target, [])  # []记录一个临时list,0记录位置保证不重复
        return self.res

    def getResult(self, nums, target, buff):
        if target == 0:
            self.res.append(list(buff))
        for i in range(len(nums)):
            if nums[i] > target or nums[i] in nums[:i]:
                continue
            buff.append(nums[i])
            self.getResult(nums[i + 1:], target - nums[i], buff)
            buff.pop()
        return

解答2

class Solution:
    def __init__(self):
        self.res = []

    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        """
            组合总和 k个数的和为n

            递归回溯，如果len(buff) == k, self.res.append(list(buff))
        """
        nums = [x for x in range(1, 10)]
        self.backTracking(nums, n, [], k)

        return self.res

    def backTracking(self, nums, n, buff, k):
        if n == 0 and len(buff) == k:
            self.res.append(list(buff))
        for i in range(len(nums)):
            if nums[i] > n or nums[i] in nums[:i]:
                continue
            buff.append(nums[i])
            self.backTracking(nums[i + 1:], n - nums[i], buff, k)
            buff.pop()

解答3

00018. n数之和

def combinationSum2(candidates, target):
    """ 组合总和, 不重复使用元素, 使用了n数之和函数 """
    candidates.sort()
    result = []
    for i in range(1, len(candidates) + 1):
        result += getSum(candidates, target, i)

    return result