【Description】
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates 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.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]
【Idea】
分析题干需求，大致手写列一下解，即知用穷举法，立即推>>DFS
https://www.jianshu.com/p/c8d1012d9e78
跟 combination sum的求解非常类似，要求额外加了一条，不能使用相同元素，因此只需在向前递进求解时，start index +1即可
另外需多加一步求解去重的操作
【Solution】
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
self.resList = []
self.DFS(candidates, target, 0, [])
return self.resList
def DFS(self, candis, target, start, value_list):
if target == 0 and value_list not in self.resList: # 求解数组去重
return self.resList.append(value_list)
length = len(candis)
for i in range(start, length):
if target >= candis[i]:
self.DFS(candis, target-candis[i], i+1 , value_list + [candis[i]])
else:
return
