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.
