Some final comments. First, in the code I posted above "push_back< S, A>" should be replaced with "push_front< S, A >", otherwise top-level sequence cannot be a list. Second, while recursive implementation is very similar to the iterative, it still generates the combinations in reverse order :) Not important for applications I can think of, but still. Finally, the performance comparison. I did it with GCC 4.2 on an Intel dual core with 4G RAM running 64-bit Ubuntu Gutsy. Iterative algorithm: 2^1 combinations: real 0m0.491s, user 0m0.432s, sys 0m0.048s 2^2 combinations: real 0m0.589s, user 0m0.488s, sys 0m0.084s 2^3 combinations: real 0m0.973s, user 0m0.624s, sys 0m0.060s 2^4 combinations: real 0m1.078s, user 0m0.824s, sys 0m0.120s 2^5 combinations: real 0m1.542s, user 0m1.424s, sys 0m0.092s 2^6 combinations: real 0m3.384s, user 0m3.012s, sys 0m0.212s 2^7 combinations: real 0m10.627s, user 0m8.781s, sys 0m0.320s 2^8 combinations: real 0m35.032s, user 0m33.582s, sys 0m0.652s 2^9 combinations: hit compiler limits, graceful exit Recursive algorithm: 2^1 combinations: real 0m0.493s, user 0m0.420s, sys 0m0.072s 2^2 combinations: real 0m0.584s, user 0m0.480s, sys 0m0.100s 2^3 combinations: real 0m0.934s, user 0m0.716s, sys 0m0.076s 2^4 combinations: real 0m1.795s, user 0m1.408s, sys 0m0.088s 2^5 combinations: real 0m5.507s, user 0m4.740s, sys 0m0.192s 2^6 combinations: real 0m29.325s, user 0m27.294s, sys 0m0.584s 2^7 combinations: overwhelmed system resources after 5min, killed