Hi Vicky.. Its O(n^K) as u are iterating over all the elements of array for each of the k element subset!!
On Monday, 8 October 2012 23:53:15 UTC+5:30, ((** VICKY **)) wrote: > > Hi, I wrote code for generating all possible sets of length k in a array > of length n. I did using recursion, but i'm not able to calc the > complexity systematically [image: :-/] Kindly help me. > 11:39 PM > > i.p {1,2,3,4,5} k =2 > o.p > Vector has : 1 2 3 4 5 > 1----> 1 2 > 2----> 1 3 > 3----> 1 4 > 4----> 1 5 > 5----> 2 3 > 6----> 2 4 > 7----> 2 5 > 8----> 3 4 > 9----> 3 5 > 10----> 4 5 > > Approach: > > Assume I have a selected and remaining set, now initially all will be > remaining set and selected set= {}. > > In first step pick 1 and grow recursion with it as root and pick 2,3,4,5 > (n-1) as possible picks. Now print those sets since k=2(base case) is > reached. > Now grow recursion with 2 as root and 3,4,5 (n-2) as possible > picks(childs) print them. Repeat till i reach 5 where i have no children > possible as rem set is empty. > > void print_all(vector<int>sel,vector<int>rem, int n){ > if(sel.size() == n) > { > static int cnt = 1; > cout<<cnt++<<"----> "; > for(int i = 0; i < n; i++) > cout<<sel[i]<<" "; > cout<<endl; > return; > sel.erase(sel.begin(),sel.end()); > } > for(int i = 0; i < rem.size(); i++) > { > > vector<int>now,curr_sel; > //for(int j = 0; j < i; j++) > // now.push_back(rem[j]); > for(int j = i+1; j<rem.size(); j++) > now.push_back(rem[j]); > // cout<<"now has : "; > //for(int i = 0; i < now.size(); i++) > // cout<<now[i]<<" "; > //cout<<endl; > for(int i = 0; i < sel.size(); i++) > curr_sel.push_back(sel[i]); > curr_sel.push_back(rem[i]); > print_all(curr_sel,now,n); > }} > > > -- > Cheers, > > Vicky > > -- 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/-/GTlxcHY8JDYJ. 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.