T******7
发帖数: 1419 | 1 // Given a set of candidate numbers (C) 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.
// 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.
// For example, given candidate set 2,3,6,7 and target 7,
// A solution set is:
// [7]
// [2, 2, 3] | k****r
发帖数: 807 | 2 back track~
recursively find the right combination
void findCom(int* s, int index, vector> result, int target,
vector tmp_sum)
if (sum(tmp_sum)==target) result.push_back(tmp_sum);
else if (sum(tmp_sum)< target) {
tmp_sum.push_back(s[index]);
findCom(s, index, result, target, tmp_sum);
tmp_sum.pop_back();
findCom(s, index+1, result, target, tmp_sum);
} | t********y
发帖数: 14 | 3 DP
public List> CombinationSum(int[] input, int value)
{
if (value <= 0) return null;
Array.Sort(input);
List>[] tmp = new List>[value + 1];
tmp[0] = new List>();
for (int i = 1; i <= value; i++)
{
List> res = new List>();
for (int j = 0; j < input.Length; j++)
{
if (i - input[j] > 0)
{
if (tmp[i - input[j]] != null && tmp[i - input[j]].
Count != 0)
{
foreach (List l in tmp[i - input[j]])
{
// this line make sure the result is in a
increase order.
//but can select same value. [2,2,3] is
allowed.
//[2,3,2] is not allowed.
if (input[j] >= l.Last())
{
List newList = new List(l);
newList.Add(input[j]);
res.Add(newList);
}
}
}
}
else if (i == input[j])
{
res.Add(new List() { input[j] });
}
else
{
// if input[j] already larget than then there
// is no need to go further.
break;
}
tmp[i] = res;
}
}
return tmp[value];
} | p*****2
发帖数: 21240 | | T******7
发帖数: 1419 | 5 Which chapter?thank u.
【在 p*****2 的大作中提到】
: 参考CC150硬币那题
| l*******b
发帖数: 2586 | | l*******b
发帖数: 2586 | 7 第4版在recursion 那一章
【在 T******7 的大作中提到】
: Which chapter?thank u.
| T******7
发帖数: 1419 | 8 Obviously ;)
【在 l*******b 的大作中提到】
: 忽然想到有负数的话就是无限多个解啦。。。
| c*****a
发帖数: 808 | | T******7
发帖数: 1419 | 10 多谢
【在 c*****a 的大作中提到】
: 150里面9.8
: 第五版
| b***i
发帖数: 3043 | 11 瞎写的
void search(int p, int S){
// b[p]is the array for the number of appearance of candidate c[p]
if (p==N){// N is the number of candidates
if (S==T){
for(int j=0;j
for(int k=0;k
cout<
cout<
}
return;
}
while(S<=T){
search(p+1, S);
b[p]++;
S=S+c[p];
}
b[p]=0;
}
【在 T******7 的大作中提到】
: // Given a set of candidate numbers (C) 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.
: // 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.
|
|
