There is a beautiful technique of generating subsets for a set of not more
than 20 elements (Why , u'll understand later as u read the code ) .
This code will just generate all the subsets of a given set . The sorted
condition and other stuff can b done easily .
for(int i=0;i<pow(2,n);i++)
{
cout<<"Subset "<<i;
for(int j=0;j<n;j++)
{
if( i & ( 1<<j) )
cout<<set[j];
}
cout<<endl;
}
As 2^n will b very huge after 18 ..19 so this method is not suitable for
n>20
On Tue, May 10, 2011 at 12:34 AM, Leopoldo Taravilse
<[email protected]>wrote:
> This is a C++ implementation assuming that vector<int> numbersOfTheSet has
> the elements of the set sorted and your result will be each vector in
> vector<vector<int> > solution. If you want to solve it with sets instead of
> vector it's the same, you only have to copy the elements of the set to a
> vector and then instead of vectors using sets in the backtracking.
>
> vector<int> numbersOfTheSet;
> vector< vector<int> > solution;
>
> void backtracking(int pos, vector<int> v)
> {
> if(pos==numbersOfTheSet.size())
> {
> solution.push_back(v);
> return;
> }
> backtracking(pos+1,v);
> v.push_back(numbersOfTheSet[pos]);
> backtracking(pos+1,v);
> return;
> }
>
> You have to call the backtracking with 0 as pos and an empty vector as v.
> This way you allways choose two options, you don't include the pos-th
> elementh of the set (and explore all options) or you include it (and explore
> all options). When the position of numbersOfTheSet is invalid (it's beyond
> the last element) you take the resulting vector and add it to the solution.
>
> I hope you understand how it works. If you want to do it with sets change
> vector<int> for set<int> and push_back for insert.
>
> --
> You received this message because you are subscribed to the Google Groups
> "google-codejam" 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/google-code?hl=en.
>
--
*
K.Rahul )
*
--
You received this message because you are subscribed to the Google Groups
"google-codejam" 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/google-code?hl=en.
