Re: [algogeeks] Re: finding all combination

2012-01-07 Thread Adolfo Ccanto
this problem is solved in O(n*s), where n is the size of Array and s is the
sum, the aproach is Dynamic Programming.

2012/1/6 saurabh singh saurab...@gmail.com

 @all Yes it is possible to find the solution using 0/1 knapsack.The
 approach would be similar as in case of LCS problem when many LCS are
 possible.Though the implementation could be a bit difficult.For each
 subproblem when the choice of dubproblems become equally beneficial start a
 new thread with both the subproblems...

 Saurabh Singh
 B.Tech (Computer Science)
 MNNIT
 blog:geekinessthecoolway.blogspot.com



 On Sat, Jan 7, 2012 at 2:01 AM, Don dondod...@gmail.com wrote:

 Given an array A[n], start by sorting the array.
 Then do something like this:

 int result[n];
 int size=0;

 void findSubset(int sum, int position=0)
 {
if (sum == 0) output(result, size);
for(int i = position; i  n; ++i)
{
if (A[i]  sum) break;
result[size++] = A[i];
 findSubset(sum-A[i], i+1);
 --size;
}
 }

 Call it like this: findSubset(4);

 Don

 On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
  There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find
 the
  possible combination which will sum to 4.
  input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
  output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as 4
 
  any approach better than O(n^2) ???

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



Re: [algogeeks] Re: finding all combination

2012-01-07 Thread atul anand
@ Adolfo  : little more detail about your approach will be helpful.



On Sat, Jan 7, 2012 at 7:07 PM, Adolfo Ccanto adol...@gmail.com wrote:

 this problem is solved in O(n*s), where n is the size of Array and s is
 the sum, the aproach is Dynamic Programming.


 2012/1/6 saurabh singh saurab...@gmail.com

 @all Yes it is possible to find the solution using 0/1 knapsack.The
 approach would be similar as in case of LCS problem when many LCS are
 possible.Though the implementation could be a bit difficult.For each
 subproblem when the choice of dubproblems become equally beneficial start a
 new thread with both the subproblems...

 Saurabh Singh
 B.Tech (Computer Science)
 MNNIT
 blog:geekinessthecoolway.blogspot.com



 On Sat, Jan 7, 2012 at 2:01 AM, Don dondod...@gmail.com wrote:

 Given an array A[n], start by sorting the array.
 Then do something like this:

 int result[n];
 int size=0;

 void findSubset(int sum, int position=0)
 {
if (sum == 0) output(result, size);
for(int i = position; i  n; ++i)
{
if (A[i]  sum) break;
result[size++] = A[i];
 findSubset(sum-A[i], i+1);
 --size;
}
 }

 Call it like this: findSubset(4);

 Don

 On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
  There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to
 find the
  possible combination which will sum to 4.
  input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
  output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as
 4
 
  any approach better than O(n^2) ???

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



[algogeeks] Re: finding all combination

2012-01-07 Thread Lucifer
@all
Check the link that i have provided above.. It solves the problem
using DP..

On Jan 7, 7:15 pm, atul anand atul.87fri...@gmail.com wrote:
 @ Adolfo  : little more detail about your approach will be helpful.







 On Sat, Jan 7, 2012 at 7:07 PM, Adolfo Ccanto adol...@gmail.com wrote:
  this problem is solved in O(n*s), where n is the size of Array and s is
  the sum, the aproach is Dynamic Programming.

  2012/1/6 saurabh singh saurab...@gmail.com

  @all Yes it is possible to find the solution using 0/1 knapsack.The
  approach would be similar as in case of LCS problem when many LCS are
  possible.Though the implementation could be a bit difficult.For each
  subproblem when the choice of dubproblems become equally beneficial start a
  new thread with both the subproblems...

  Saurabh Singh
  B.Tech (Computer Science)
  MNNIT
  blog:geekinessthecoolway.blogspot.com

  On Sat, Jan 7, 2012 at 2:01 AM, Don dondod...@gmail.com wrote:

  Given an array A[n], start by sorting the array.
  Then do something like this:

  int result[n];
  int size=0;

  void findSubset(int sum, int position=0)
  {
     if (sum == 0) output(result, size);
     for(int i = position; i  n; ++i)
     {
         if (A[i]  sum) break;
         result[size++] = A[i];
          findSubset(sum-A[i], i+1);
          --size;
     }
  }

  Call it like this: findSubset(4);

  Don

  On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
   There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to
  find the
   possible combination which will sum to 4.
   input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
   output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as
  4

   any approach better than O(n^2) ???

  --
  You received this message because you are subscribed to the Google
  Groups Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

   --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

   --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



Re: [algogeeks] Re: finding all combination

2012-01-07 Thread atul anand
@Don : what would be the complexity of your alogithm??

On Sat, Jan 7, 2012 at 2:01 AM, Don dondod...@gmail.com wrote:

 Given an array A[n], start by sorting the array.
 Then do something like this:

 int result[n];
 int size=0;

 void findSubset(int sum, int position=0)
 {
if (sum == 0) output(result, size);
for(int i = position; i  n; ++i)
{
if (A[i]  sum) break;
result[size++] = A[i];
 findSubset(sum-A[i], i+1);
 --size;
}
 }

 Call it like this: findSubset(4);

 Don

 On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
  There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find
 the
  possible combination which will sum to 4.
  input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
  output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as 4
 
  any approach better than O(n^2) ???

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



[algogeeks] Re: finding all combination

2012-01-07 Thread Lucifer
@atul..

So following the above previous posted link.. the time complexity
would be 4*n = O(n)...
[ just adding it here, because i saw that u went thru the link.. :)]

On Jan 7, 9:30 pm, atul anand atul.87fri...@gmail.com wrote:
 @Don : what would be the complexity of your alogithm??







 On Sat, Jan 7, 2012 at 2:01 AM, Don dondod...@gmail.com wrote:
  Given an array A[n], start by sorting the array.
  Then do something like this:

  int result[n];
  int size=0;

  void findSubset(int sum, int position=0)
  {
     if (sum == 0) output(result, size);
     for(int i = position; i  n; ++i)
     {
         if (A[i]  sum) break;
         result[size++] = A[i];
          findSubset(sum-A[i], i+1);
          --size;
     }
  }

  Call it like this: findSubset(4);

  Don

  On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
   There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find
  the
   possible combination which will sum to 4.
   input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
   output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as 4

   any approach better than O(n^2) ???

  --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



Re: [algogeeks] Re: finding all combination

2012-01-07 Thread atul anand
To remove duplicate combination in DON code...here is the modified code:-

Given an array A[n], start by sorting the array.
Then do something like this:

int result[n];
int size=0;
int prev=-1; // added

void findSubset(int sum, int position=0)
{
   if (sum == 0) output(result, size);
   for(int i = position; i  n; ++i)
   {
   if (A[i]  sum) break;
   if(prev!=A[i])  // added
   {
  result[size++] = A[i];
  findSubset(sum-A[i], i+1);
  prev=A[i];  // added
   --size;
   }
   }
}

Call it like this: findSubset(4);

On Sat, Jan 7, 2012 at 10:25 PM, atul anand atul.87fri...@gmail.com wrote:

 @Don : your algorithm will works but it will print lots of duplicate
 combination.




 On Sat, Jan 7, 2012 at 10:00 PM, atul anand atul.87fri...@gmail.comwrote:

 @Don : what would be the complexity of your alogithm??


 On Sat, Jan 7, 2012 at 2:01 AM, Don dondod...@gmail.com wrote:

 Given an array A[n], start by sorting the array.
 Then do something like this:

 int result[n];
 int size=0;

 void findSubset(int sum, int position=0)
 {
if (sum == 0) output(result, size);
for(int i = position; i  n; ++i)
{
if (A[i]  sum) break;
result[size++] = A[i];
 findSubset(sum-A[i], i+1);
 --size;
}
 }

 Call it like this: findSubset(4);

 Don

 On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
  There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to
 find the
  possible combination which will sum to 4.
  input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
  output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as
 4
 
  any approach better than O(n^2) ???

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.





-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



Re: [algogeeks] Re: finding all combination

2012-01-07 Thread saurabh singh
Sorry for being offtopic but  yes if anyone proposes a polynomial time
algorithm(which can work for all cases) he is entitled to a prize money of
1 million. http://en.wikipedia.org/wiki/Millennium_Prize_Problems

Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com



On Sat, Jan 7, 2012 at 11:46 PM, Gene gene.ress...@gmail.com wrote:

 If you have an O(n^2) algorithm, you will be famous because you will
 have proven that P=NP.  As has been pointed out, this is the subset
 sum problem, well known to be NP hard.

 It is only weakly NP hard, though.  There is a simple pseudo-
 polynomial time DP algorithm.  Let S(n, k) be a boolean function true
 iff there is a subset of elements that sum to n using only elements
 1,2,...,k.

 Then S(n,k) = S(n,k-1) or S(n - a[k], k-1) for n,k0.  The base cases
 are S(0,k)=true for k=0 and S(n,0)= false for n0.  The intuition
 here is you either skip usiong the k'th item in the subset or use
 it.

 This just tells you whether a subset exists.  It's easy to find the
 subset elements with back pointers in the DP table, which will form a
 tree rooted at S(n, N) where the array has N elements.  Each root-leaf
 path in the tree will be a valid subset.

 This algorithm is polynomial in the _size_ of the elements, which is
 exponential time by the normal definition, but can be useful if data
 are small.  That's why it's called pseudo-polynomial time.



 On Jan 3, 12:26 pm, atul anand atul.87fri...@gmail.com wrote:
  There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find
 the
  possible combination which will sum to 4.
  input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
  output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as 4
 
  any approach better than O(n^2) ???

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



[algogeeks] Re: finding all combination

2012-01-06 Thread sravanreddy001
@atul007: When you mean n^2 solution.. did you mean the DP which actually 
is 2^n??

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/MrOfjqZKk8YJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



Re: [algogeeks] Re: finding all combination

2012-01-06 Thread atul anand
@shady , prakash : we have to find all combination , not one so could you
providelittle more explanation by using 0-1 knapsack.

@ sravanreddy001: yeah it should be O(2^n).




On Fri, Jan 6, 2012 at 8:07 PM, sravanreddy001 sravanreddy...@gmail.comwrote:

 @atul007: When you mean n^2 solution.. did you mean the DP which actually
 is 2^n??

  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/MrOfjqZKk8YJ.

 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



[algogeeks] Re: finding all combination

2012-01-06 Thread Lucifer
@ The following link might help..

http://groups.google.com/group/algogeeks/browse_thread/thread/8a58ea05c96f811b?hl=en#

Basicaly if A[N, Wmax] = 1, then find all subsets using backtracking..
where,
N = no. of elements,
Wmax = 4...

On Jan 6, 7:50 pm, atul anand atul.87fri...@gmail.com wrote:
 @shady , prakash : we have to find all combination , not one so could you
 providelittle more explanation by using 0-1 knapsack.

 @ sravanreddy001: yeah it should be O(2^n).

 On Fri, Jan 6, 2012 at 8:07 PM, sravanreddy001 
 sravanreddy...@gmail.comwrote:







  @atul007: When you mean n^2 solution.. did you mean the DP which actually
  is 2^n??

   --
  You received this message because you are subscribed to the Google Groups
  Algorithm Geeks group.
  To view this discussion on the web visit
 https://groups.google.com/d/msg/algogeeks/-/MrOfjqZKk8YJ.

  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from this group, send email to
  algogeeks+unsubscr...@googlegroups.com.
  For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



Re: [algogeeks] Re: finding all combination

2012-01-06 Thread sravanreddy001
@atul007: the 0-1 knapsack is a special case of subset sum problem,  (and.. 
i don't think its easy to find all the solutions using 0/1 knapsack.. )

@shady: is it possible?

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/2xspry_EJxoJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



[algogeeks] Re: finding all combination

2012-01-06 Thread Don
Given an array A[n], start by sorting the array.
Then do something like this:

int result[n];
int size=0;

void findSubset(int sum, int position=0)
{
if (sum == 0) output(result, size);
for(int i = position; i  n; ++i)
{
if (A[i]  sum) break;
result[size++] = A[i];
findSubset(i+1, sum-A[i]);
--size;
}
}

Call it like this: findSubset(4);

Don


On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
 There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find the
 possible combination which will sum to 4.
 input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
 output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as 4

 any approach better than O(n^2) ???

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



[algogeeks] Re: finding all combination

2012-01-06 Thread Don
Given an array A[n], start by sorting the array.
Then do something like this:

int result[n];
int size=0;

void findSubset(int sum, int position=0)
{
if (sum == 0) output(result, size);
for(int i = position; i  n; ++i)
{
if (A[i]  sum) break;
result[size++] = A[i];
findSubset(sum-A[i], i+1);
--size;
}
}

Call it like this: findSubset(4);

Don

On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
 There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find the
 possible combination which will sum to 4.
 input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
 output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as 4

 any approach better than O(n^2) ???

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



Re: [algogeeks] Re: finding all combination

2012-01-06 Thread saurabh singh
@all Yes it is possible to find the solution using 0/1 knapsack.The
approach would be similar as in case of LCS problem when many LCS are
possible.Though the implementation could be a bit difficult.For each
subproblem when the choice of dubproblems become equally beneficial start a
new thread with both the subproblems...
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com



On Sat, Jan 7, 2012 at 2:01 AM, Don dondod...@gmail.com wrote:

 Given an array A[n], start by sorting the array.
 Then do something like this:

 int result[n];
 int size=0;

 void findSubset(int sum, int position=0)
 {
if (sum == 0) output(result, size);
for(int i = position; i  n; ++i)
{
if (A[i]  sum) break;
result[size++] = A[i];
 findSubset(sum-A[i], i+1);
 --size;
}
 }

 Call it like this: findSubset(4);

 Don

 On Jan 3, 5:26 am, atul anand atul.87fri...@gmail.com wrote:
  There is integer array like {1,2,4,5,6,1,2,4,3,5,7,2,1}. I want to find
 the
  possible combination which will sum to 4.
  input : {1,2,4,5,6,1,2,4,3,5,7,2,1}
  output : {1,1,2}, {2,2}, {3,1}, {1,2,1}{4}...etc which make the sum as 4
 
  any approach better than O(n^2) ???

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.



[algogeeks] Re: finding all combination

2012-01-05 Thread WgpShashank
@atul ,FYI, another naive approach will to generate the all subset of given 
set , thats the power set , has complexity O(n*2^n) , obviously not better 
then upper one , but still you can try to figure out the sum problem ,  you 
will get some relation to DP.


Thanks
Shashank Mani 
Computer Science
Birla Institute of Technology,Mesra
*http://shashank7s.blogspot.com*

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/Di1eSEnE8XQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.