I only solved the following problem for reference (441 – Lotto). It basically requires the generation everyone $ k $Combinations of $ n $ items

`void backtrack(std::vector`& a,
int index,
std::vector& sel,
int selections) {
if (selections == 6) { // k is always 6 for 441 - lotto
//print combination
return;
}
if (index >= a.size()) { return; } // no more elements to choose from
// two choices
// (1) select a(index)
sel(index) = true;
backtrack(a, index+1, sel, selections+1);
// (2) don't select a(index)
sel(index) = false;
backtrack(a, index+1, sel, selections);
}

I wanted to analyze my own code. I know that I am making a call at the top level (level = 0). On the next level (level = 1) of the recursion I have to trace two calls back. At the next level, I have $ 2 ^ 2 $ Calls. The last level would have been $ 2 ^ n $ Sub-problems. We do for every call $ O (1) $ Work of selecting or not selecting the item. So the total time would be $ 1 + 2 + 2 ^ 2 + 2 ^ 3 + … + 2 ^ n = 2 ^ {n + 1} – 1 = O (2 ^ {n}) $

I've been thinking since we started generating $ binom {n} {k} $ Combinations that there could be a better algorithm with a better runtime since then $ binom {n} {k} = O (n ^ 2) $ or maybe my algorithm is wasteful and there is a better way? or is my analysis really incorrect? Which is it?