[LeetCode] 39. Combination Sum

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:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 

[
  [7],
  [2, 2, 3]
]

可以把這題想成 找錢問題, 現在 要找客人 7 塊, 手上有 面額 2,3,6,7 的硬幣無限個 請問有幾種找法. 因為是找錢 所以[2,2,3] 跟 [2,3,2] 是一樣的.

想法上還是 dfs,

line_8 : 錢多找了, 答案一定不對. 直接就放棄不找了 加快收尋速度
line_10 : path 做深copy,
line_14 : n[i:] 就是避免循環的時候 出現重複選的情況. [2,2,3] 跟 [2,3,2] 就是在這被過濾掉的