40-combination-sum-ii.md

40. Combination Sum II - 组合总和 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]
]

---

题目标签：Array / Backtracking

题目链接：LeetCode / LeetCode中国

题解

要列出所有组合，显然可以暴力，因此可以用递归，主要难点在于如何保证不重复。

首先规定取了一个元素后，只能取其右侧的元素。但是，重复元素怎么处理呢？这里可以先进行排序，每次通过检查最后一个结果来判别重复。

Language	Runtime	Memory
python3	104 ms	N/A

class Solution:
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        res = []
        for i, num in enumerate(candidates):
            if num == target and (not res or res[-1][0] != num):
                res.append([num])
            elif num < target and (not res or res[-1][0] != num):
                for r in self.combinationSum2(candidates[i+1:], target-num):
                    res.append([num, *r])
        return res