Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
这道题和Leetcode 39差不多，区别是一个元素只能用一次，所以L27里面用了candidates[i+1:]。另外需要注意的是，[1a,2,5] 和 [1b,2,5]在结果中应被视为重复解而去掉一个。所以用了L13-L16。
class Solution(object):
def combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
candidates.sort() res = []
self.helper(candidates, target, res, []) ans = []
for elem in res:
if elem not in ans:
ans.append(elem) return ans def helper(self, candidates, target, res, line):
if target == 0:
res.append([x for x in line]) for i,x in enumerate(candidates):
if x <= target:
line.append(x)
self.helper(candidates[i+1:], target - x, res, line)
line.pop()