avatar
leetcode上一题,求正解# JobHunting - 待字闺中
l*1
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]
avatar
q*c
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 <}
avatar
s*n
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);
}
avatar
l*1
4
貌似这种的时间复杂度极高啊,而且用recursion的话,空间复杂度也很大啊。有没有
什么巧妙的算法呢?像2sum可以在O(nlogn) constant space得到。还是巧妙的算法对于
interview太过复杂,这个就足够了?谢谢!
avatar
i*e
5
楼上的几位都没处理重复,output 仍然有重复组合。
avatar
j*j
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 仍然有重复组合。
avatar
s*n
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 仍然有重复组合。
avatar
a*g
8
这个和硬币算钱是一样的么
avatar
z*n
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;

avatar
i*e
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 的大作中提到】
: 如果有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;

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。