leetcode上一题，求正解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode上一题，求正解

leetcode上一题，求正解# JobHunting - 待字闺中

l*12012-03-12 07:03

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]

q*c2012-03-12 07:03

2 楼

帖个我写的，欢迎指正。
void getCandidates(int data[], int size, int sum)
{
vector list;
for(int i = 0; i < size; ++i) {
list.clear();
getSums(data, size, i, sum, list);
}
}
void getSums(int data[], int size, int start, int k, vector& list)
{

if(k == 0)
printList(list);
else if(k < 0)
return;
else{
list.push_back(data[start]);
k = k - data[start];
for(int j = start; j < size; ++j) {
if(k == data[j]) {
list.push_back(data[j]);
printList(list);
list.pop_back();
}
}
if(k >= 0) {
getSums(data, size, start, k, list);
}
list.pop_back();
}
}
void printList(vector& list)
{
for(int i = 0; i < list.size(); ++i){
cout << list[i] << " ";
}
cout <}

s*n2012-03-12 07:03

3 楼

写了几遍才对。。。
#include
#define exchangenum(a,b) {a^=b;b^=a;a^=b;}
void print(int* a, int count, int sum, int* out, int outindex)
{
if (sum==0) {
for (int i=0; iprintf("\n");
return;
}
if (count==0) return;
out[outindex] = a[0];
print(a+1, count-1, sum-a[0], out, outindex+1);
print(a+1, count-1, sum, out, outindex);
}
int main(int argc, char** argv)
{
int a[5] = {1,3,4,2,6};
int sum = 7;
int out[5];
print(a, sizeof(a)/sizeof(a[0]), sum, out, 0);
}

l*12012-03-12 07:03

4 楼

貌似这种的时间复杂度极高啊，而且用recursion的话，空间复杂度也很大啊。有没有
什么巧妙的算法呢?像2sum可以在O(nlogn) constant space得到。还是巧妙的算法对于
interview太过复杂，这个就足够了？谢谢！

i*e2012-03-12 07:03

5 楼

楼上的几位都没处理重复，output 仍然有重复组合。

j*j2012-03-12 07:03

6 楼

我的解法， test case都通过了
vector > combinationSumrec(vector candidates, int start,
int end,int target){
vector > toreturn;
if (target == 0){
vector temp;
toreturn.push_back(temp);
return toreturn;
}
if (targetreturn toreturn;
if (start > end)
return toreturn;
if (start == end){
if (target%(candidates[start]) == 0){
int product = target/candidates[start];
vector temp;
for (int k=0;ktemp.push_back(candidates[start]);
toreturn.push_back(temp);
}
return toreturn;
}
vector > nolast = combinationSumrec(candidates, start,
end-1,target);
vector > withlast = combinationSumrec(candidates, start,
end,target-candidates[end]);
for(int i=0;iwithlast[i].push_back(candidates[end]);
toreturn.push_back(withlast[i]);
}
for(int j=0;j toreturn.push_back(nolast[j]);
}
return toreturn;

}
vector > combinationSum(vector &candidates, int target)
{
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > allsum;
if (candidates.size() == 0)
return allsum;
sort(candidates.begin(),candidates.end());
allsum = combinationSumrec(candidates,0,candidates.size()-1,target);
return allsum;
}

【在 i**********e 的大作中提到】

: 楼上的几位都没处理重复，output 仍然有重复组合。

s*n2012-03-12 07:03

7 楼

如果有1,3,3,4,5，3重复，则需要特别处理，2个连续的3，分别处理3,3,4... 3,4... ,4.... 三种情况，应该没比我这程序更简短的了吧。：）
#include
void print(int* a, int count, int sum, int* out, int outindex)
{
if (sum==0) {
for (int i=0; iprintf("\n");
return;
}
if (sum<0 || count==0) return;
int samea=1;
for (; sameafor (int k=0; k<=samea; k++) {
print(a+samea, count-samea, sum-a[0]*(k), out, outindex+k);
out[outindex+k] = a[0];
}
}
int main(int argc, char** argv)
{
int a[6] = {1,2,3,3,4,6};
int sum = 8;
int out[6];
print(a, sizeof(a)/sizeof(a[0]), sum, out, 0);
}

【在 i**********e 的大作中提到】

: 楼上的几位都没处理重复，output 仍然有重复组合。

a*g2012-03-12 07:03

8 楼

这个和硬币算钱是一样的么

z*n2012-03-12 07:03

9 楼

强！学习了：）
另外，要先sort一下，不然会有重复。

. ,4.... 三种情况，应该没比我这程序更简短的了吧。：）

【在 s******n 的大作中提到】

: 如果有1,3,3,4,5，3重复，则需要特别处理，2个连续的3，分别处理3,3,4... 3,4... ,4.... 三种情况，应该没比我这程序更简短的了吧。：）
: #include
: void print(int* a, int count, int sum, int* out, int outindex)
: {
: if (sum==0) {
: for (int i=0; i: printf("\n");
: return;
: }
: if (sum<0 || count==0) return;

i*e2012-03-12 07:03

10 楼

很好，不过你这个是解决另一个问题的变种。（还有一个小bug会产生重复，例如
[2,5,2,1,2], sum=5, 你的答案是 [[2,1,2],[5],[2,1,2],[2,2,1]]，有多个重复。
只要排序一下就好了）。
问题里说明：
The same repeated number may be chosen from C unlimited number of times.
也就是说同一个元素可以取出多次。不过这个思路也很类似。
这题的总结在这里：
http://www.leetcode.com/2010/09/print-all-combinations-of-numbe

. ,4.... 三种情况，应该没比我这程序更简短的了吧。：）

【在 s******n 的大作中提到】