This is a very standard algorithm called subset sum problem and as mentioned above DP gives an efficient solution as the expense of extra space.
On Oct 11, 9:14 am, abhishek sharma <abhishek.p...@gmail.com> wrote: > yea DP will be O(given no * n) if all array entries are positive and the > given no is non negative. > > On Mon, Oct 10, 2011 at 11:09 PM, anshu mishra > <anshumishra6...@gmail.com>wrote: > > > > > > > > > > > the simplest code could be for this question is > > > void printAllSubsetSum(int ar[], int n, int x) > > { > > for (i = 0; i < (1<<n); i++) > > { > > int sum = 0; > > for (j = 0; j < n; j++) > > { > > if ( (1 << j) && i) sum += ar[j]; > > } > > if (sum == x) > > { > > for (j = 0; j < n; j++) > > { > > if ( (1 << j) && i) printf("%d ", ar[j]); > > } > > printf("\n"); > > } > > } > > } > > > Time complexity O(2^n) > > > this can be solved using DP in O(n * given number); > > > -- > > 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. > > -- > Nice Day > > Abhishek Sharma > Bachelor of Technology > IIT Kanpur (2009) -- 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.