This should be O(2^n)
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int sol[1000];
void solve(int pos, int k) {
for(int i = 0; i < k; i++) printf("%d, ", sol[i]);
putchar('\n');
for(int i = pos; i < n; i++) {
sol[k] = i+1;
solve(i+1, k+1);
}
}
int main() {
scanf("%d", &n);
solve(0, 0);
}
On Jul 27, 8:33 pm, Ankur Garg <[email protected]> wrote:
> Hi
>
> The solution in the link is of complexity (n*2^n))
>
> Does anyone know any better solution ?
>
> Regards
> Ankur
> On Tue, Jul 26, 2011 at 11:10 PM, rajeev bharshetty
> <[email protected]>wrote:
>
>
>
> > @Ankur The link does has a very good explanation. Nice solution :)
>
> > On Tue, Jul 26, 2011 at 10:47 PM, Kunal Patil <[email protected]> wrote:
>
> >> @Ankur Garg: Nice explanation at the link given by u...
>
> >> On Tue, Jul 26, 2011 at 10:35 PM, Ankur Garg <[email protected]>wrote:
>
> >>> Check this
>
> >>>http://codesam.blogspot.com/2011/03/find-all-subsets-of-given-set.html
>
> >>> On Tue, Jul 26, 2011 at 9:41 PM, Vishal Thanki
> >>> <[email protected]>wrote:
>
> >>>> Here is the working code..
>
> >>>> #include <stdio.h>
> >>>> #include <stdlib.h>
> >>>> int a[] = {1,2,3,4,5};
> >>>> #define ARRLEN(a) (sizeof(a)/sizeof(a[0]))
> >>>> void print_comb(int len)
> >>>> {
> >>>> int tlen = len;
> >>>> int i, j, k;
> >>>> int al = ARRLEN(a);
> >>>> for (i = 0; i < al; i++) {
> >>>> for (j=i+len-1; j<al;j++) {
> >>>> for (k = i; k < i+len-1; k++) {
> >>>> printf("%d ", a[k]);
> >>>> }
> >>>> printf("%d\n", a[j]);
> >>>> }
> >>>> }
> >>>> }
>
> >>>> int main(int argc, char *argv[])
> >>>> {
> >>>> int len = atoi(argv[1]);
> >>>> print_comb(len);
> >>>> return 0;
> >>>> }
>
> >>>> On Tue, Jul 26, 2011 at 5:18 PM, praneethn <[email protected]>
> >>>> wrote:
>
> >>>> > check this link:
>
> >>>> > *http://www.stefan-pochmann.info/spots/tutorials/sets_subsets/*
>
> >>>> > On Tue, Jul 26, 2011 at 11:59 AM, sumit <[email protected]>
> >>>> wrote:
>
> >>>> >> Given an array of size n, print all the possible subset of array of
> >>>> >> size k.
> >>>> >> eg:-
> >>>> >> input:
> >>>> >> a[]={1,2,3,4}, k = 2
> >>>> >> output:
> >>>> >> 1,2
> >>>> >> 1,3
> >>>> >> 1,4
> >>>> >> 2,3
> >>>> >> 2,4
> >>>> >> 3,4
>
> >>>> >> --
> >>>> >> You received this message because you are subscribed to the Google
> >>>> Groups
> >>>> >> "Algorithm Geeks" group.
> >>>> >> To post to this group, send email to [email protected].
> >>>> >> To unsubscribe from this group, send email to
> >>>> >> [email protected].
> >>>> >> 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 [email protected].
> >>>> > To unsubscribe from this group, send email to
> >>>> > [email protected].
> >>>> > 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 [email protected].
> >>>> To unsubscribe from this group, send email to
> >>>> [email protected].
> >>>> 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 [email protected].
> >>> To unsubscribe from this group, send email to
> >>> [email protected].
> >>> 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 [email protected].
> >> To unsubscribe from this group, send email to
> >> [email protected].
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Regards
> > Rajeev N B <http://www.opensourcemania.co.cc>
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
