Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[ [7], [2, 2, 3] ]
一般跟求combiantion相关的题目基本上都会用到DFS。这里需要注意的是，用L22可以代替L23-L25。因为L22并没有改变 line， 所以line+[x]在内存中其实被另外的单独存储，所以不用line.pop()。
1 class Solution(object): 2 def combinationSum(self, candidates, target): 3 """ 4 :type candidates: List[int] 5 :type target: int 6 :rtype: List[List[int]] 7 """ 8 candidates.sort() 9 10 res = [] 11 line = [] 12 self.helper(candidates, target, res, line) 13 return res 14 15 def helper(self, candidates, target, res, line): 16 if target == 0: 17 res.append([x for x in line]) 18 return 19 20 for i, x in enumerate(candidates): 21 if x <= target: 22 # self.helper(candidates[i:], target-x, res, line+[x]) 23 line.append(x) 24 self.helper(candidates[i:], target-x, res, line) 25 line.pop() 26
原文：http://www.cnblogs.com/lettuan/p/6250984.html