The problem is to generate all possible unique selections of n numbers from a given set of size > n.

I've pretty much done it by brute force, as the number of final results should be same whichever way I choose. If a better way is not possible, I'd like suggestions about simple optimizations.

I noticed that having the return container a deque makes this much faster than if a vector or list is used. Why ?Code:std::deque<std::set<int>> find_combinations(const std::set<int>& U,unsigned int n) { std::deque<std::set<int>> result; if(n<1 || U.size()<n)//Nothing Happens Here ! {} else if(n==1) // The Universal input set is broken up and redistributed. { for(auto x:U) result.push_back(std::set<int>({x})); } else // Recursion FTW, no comments !! { std::set<int> temp(U); for(auto x:U) { temp.erase(x); auto partial_result = find_combinations(temp,n-1); for(auto& y:partial_result) y.insert(x); result.insert ( std::begin(result), std::begin(partial_result), std::end(partial_result) ); } } return result; }

Also, is it worth the trouble trying to do it iteratively?

Finally, can anyone help me determining the complexity of this function ?

(I think it is something near (log base n U.size() )^ n) but I'm probably very very wrong about that.)

Btw, here is a main you can use to test it.

Code:int main(int argc,char** argv) { std::set<int> input; for(int i=0;i<atoi(argv[1]);i++) input.insert(i); auto foo = find_combinations(input,atoi(argv[2])); // for(auto x:foo) //displaying results // { // for(auto y:x) // std::cout<<y<<'\t'; // std::cout<<std::endl; // } }