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]
]
解析:
思路比较简单,因为这几天一直在练回溯(backtracing),所以基本思路就是target - 当前元素,再调用函数寻找,当target = 0时,此时这个答案可作为答案集的一种,但是对比大神的答案,我找到了我两点没想到的地方:
1. 我们应该跳过原数集中重复的元素,所以一开始还应该对原数集进行sort
2. 我们要做不回头查找,以防有重复答案,即在[i , n - i] 查找符合要求的解,这样的话我们就需要一个回溯的函数中就要包含一个 i 作为标志位
代码如下: