【LeetCode】0040 组合总数II

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

# -*- coding:utf-8 -*-

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        n = len(candidates)
        res = []
        def backtrack(i, tmp_sum, tmp):
            """
            回溯法
            :param i: 当前选择的索引
            :param tmp_sum: 当前已选择所有数的和
            :param tmp: 当前已选择数的列表
            :return:
            """
            if tmp_sum > target or i == n + 1:
                return
            if tmp_sum == target:
                res.append(tmp)
                return
            for j in range(i, n):
                if tmp_sum + candidates[j] > target:
                    break
                backtrack(j + 1, tmp_sum + candidates[j], tmp + [candidates[j]])
        backtrack(0, 0, [])
        res_final = []
        # 去重
        for each in res:
            if each not in res_final:
                res_final.append(each)
        return res_final
if __name__ == '__main__':
    # candidates = [10, 1, 2, 7, 6, 1, 5]
    # target = 8
    candidates = [2, 5, 2, 1, 2]
    target = 5
    print(Solution().combinationSum(candidates, target))

思路：这道题和上一道题十分类似，不同的就是需要做一些处理。

比如上一道题允许一个数字使用多次，因此递归调用的时候依然传入j，但是这道题不允许重复使用，因此下一次查找应该是j+1次。

上一道题题中写到没有重复元素，这一道题允许重复元素，因此在返回前要做一次去重。

上一道题边界条件是i==n，理由和第一条差不多，因为是传入j，而这道题是j+1，因此边界条件也应该变成n+1。