LeetCode 040 Combination Sum II

LeetCode

<div>

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

<pre>Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [ [1,1,6], [1,2,5], [1,7], [2,6] ] </pre>

Example 2:

<pre>Input: candidates = [2,5,2,1,2], target = 5 Output: [ [1,2,2], [5] ] </pre>

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

</div>

题目大意：

求组合和等于目标。元素不可复用且结果去重

解题思路：

用组合模板，先排序

解题步骤：

N/A

注意事项：

1. 类似于Leetcode 39，有两点不同。要去重，i > start并不是i > 0, 且比较前一个元素
2. 因为元素不可重复，下一轮递归i + 1

Python代码：

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
	candidates.sort()
	res = []
	self.dfs(candidates, 0, target, [], res)
	return list(res)

def dfs(self, candidates, start, target, path, res): # [1, 2], 0, 0, [1, 1], [1, 1]
	if target < 0:
		return
	if target == 0:
		res.append(list(path))
		return
	for i in range(start, len(candidates)): # [2]
		if i > start and candidates[i - 1] == candidates[i]:
			continue
		path.append(candidates[i]) # [1,1]
		self.dfs(candidates, i + 1, target - candidates[i], path, res)
		path.pop()

算法分析：

时间复杂度为<code>O(2ⁿ)</code>，空间复杂度O(n)