Given a set of candidate numbers (C) and a target number (T), find all unique combinations inC_where the candidate numbers sums toT_.
Thesamerepeated number may be chosen from_C_unlimited number of times.
Example
Given candidate set[2,3,6,7]and target7, a solution set is:
[7]
[2, 2, 3]
Notice
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
分析：
单数可重复取问题
要去重，用set。
要排序为了后面target<num[i]可以直接返回，因为后面更大无需比了。
class Solution:
"""
@param candidates: A list of integers
@param target: An integer
@return: A list of lists of integers
"""
def combinationSum(self, candidates, target):
# write your code here
candidates = sorted(list(set(candidates)))#排序和去重复，比如3个1只要一个
ret = []
self.dfs(candidates, target, ret, [], 0)
return ret
def dfs(self,candidates, target, ret, path, start):
if target == 0:
ret.append(list(path))
for i in range(start,len(candidates)):
if candidates[i] > target:#此处可以直接返回因为已排序，当前i不行的话后面更大
return
path.append(candidates[i])
self.dfs(candidates, target-candidates[i], ret, path, i)
path.pop()