f*********m
发帖数: 726 | 1 Print All Combinations of a Number as a Sum of Candidate Numbers
（http://www.leetcode.com/2010/09/print-all-combinations-of-number-as-sum.html）
原文如下，稍作修改（把target 从7该为9）：
“To search for all combination, we use a backtracking algorithm. Here, we
use the above example of candidate={2,3,6,7} and target=9.
First, we start with a sum of 0. Then, we iterate over all possibilities
that can be added to sum, which yields the possible set of sum={2,3,6,7}.
Assume now that sum=2, we continue adding all possible candidate numbers {2,
3,6,7} to sum=2, which yields sum={4,5,8,9}. Each step we have to use an
array to keep track of all the indices of candidate numbers that add to the
current sum, so that we can print the combination later. The next case would
be sum=3. We look at all possible candidate numbers {3,6,7} to be added to
sum=3, which yields sum={6,9,10}. Note that there is no need to look
backward (ie, candidate numbers that are smaller than 3), as this would only
yield duplicate results. We keep doing this recursively, until we reach the
conditions below, where we stop.
。。。
”
看原文，sum只是candidate number中的一个，然后取出来candidate相加一次，得到一
个新的sum数组，比如，sum=3,则sum数组={6,9,10}。那么如何保证3可以被加3次，使
得9=3+3+3?
原文说“We keep doing this recursively”，请问如何recursive?
谢谢。 | p*****2
发帖数: 21240 | | f*********m
发帖数: 726 | | p*****2
发帖数: 21240 | 4 target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)
不就是在一个数组里找subset，使得sum为target吗？ | j********e
发帖数: 1192 | 5 正好做了这道题。
其实就是recursive，不过先把candidate排序，然后确保输出唯一结果
（例如一旦使用了3，以后就不能再使用比3小的数）
class Solution {
public:
vector > results;
void combinationSum(int sum, int target, const vector &cand,
int index, vector &queue) {
if(sum == target) {
results.push_back(queue);
return;
}
for(int i = index; i
if(sum + cand[i] <= target) {
queue.push_back(cand[i]);
combinationSum(sum + cand[i], target, cand,
i, queue);
queue.pop_back();
}
else
break;
}
}
vector > combinationSum(vector &candidates, int
target) {
vector cand = candidates;
vector queue;
results.clear();
sort(cand.begin(), cand.end());
combinationSum(0, target, cand, 0, queue);
return results;
}
};
2,
the
【在 f*********m 的大作中提到】
: Print All Combinations of a Number as a Sum of Candidate Numbers
: （http://www.leetcode.com/2010/09/print-all-combinations-of-number-as-sum.html）
: 原文如下，稍作修改（把target 从7该为9）：
: “To search for all combination, we use a backtracking algorithm. Here, we
: use the above example of candidate={2,3,6,7} and target=9.
: First, we start with a sum of 0. Then, we iterate over all possibilities
: that can be added to sum, which yields the possible set of sum={2,3,6,7}.
: Assume now that sum=2, we continue adding all possible candidate numbers {2,
: 3,6,7} to sum=2, which yields sum={4,5,8,9}. Each step we have to use an
: array to keep track of all the indices of candidate numbers that add to the
| f*********m
发帖数: 726 | 6 但是数组里的元素可以重复出现，比如数组中只含有一个2，而结果可以是2+2+3.所以
还是有些区别吧？
【在 p*****2 的大作中提到】
: target is 7, candidate is 2,3,6,7
: output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)
: 不就是在一个数组里找subset，使得sum为target吗？
| p*****2
发帖数: 21240 | 7
可以重复也没关系。道理差不多呀。就是取0个，或者取多个。然后往后找。
【在 f*********m 的大作中提到】
: 但是数组里的元素可以重复出现，比如数组中只含有一个2，而结果可以是2+2+3.所以
: 还是有些区别吧？
| e***s
发帖数: 799 | | a********d
发帖数: 195 | 9 是不是150上硬币的题加个传入的数组和打印条件？ | f*********m
发帖数: 726 | 10 这道题需要排序吗？leetocode中说不需要（http://www.leetcode.com/2010/09/print-all-combinations-of-number-as-sum.html）
【在 j********e 的大作中提到】
: 正好做了这道题。
: 其实就是recursive，不过先把candidate排序，然后确保输出唯一结果
: （例如一旦使用了3，以后就不能再使用比3小的数）
: class Solution {
: public:
: vector > results;
:
: void combinationSum(int sum, int target, const vector &cand,
: int index, vector &queue) {
: if(sum == target) {
| f*********m
发帖数: 726 | 11 combinationSum(sum + cand[i], target, cand,i, queue);为什么不是
combinationSum(sum + cand[i], target, cand,i+1, queue)?
【在 j********e 的大作中提到】
: 正好做了这道题。
: 其实就是recursive，不过先把candidate排序，然后确保输出唯一结果
: （例如一旦使用了3，以后就不能再使用比3小的数）
: class Solution {
: public:
: vector > results;
:
: void combinationSum(int sum, int target, const vector &cand,
: int index, vector &queue) {
: if(sum == target) {
|
|
