What is the running time of generating all $k$ combinations of $n$ items $\binom{n}{k}$?


I was solving the following problem, just for reference (441 – Lotto). It basically requires the generation all $ k$ -combinations of $ n$ items

void backtrack(std::vector<int>& a,                int index,                std::vector<bool>& 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 at the top level (level = 0), I’m making one call. At the next level (level=1) of recursion, I have two calls to backtrack. At the following level, I have $ 2^2$ calls. The last level would have $ 2^n$ subproblems. For each call, we make $ O(1)$ work of selecting or not selecting the element. So the total time would be $ 1+2+2^2+2^3+…+2^n = 2^{n+1} – 1 = O(2^{n})$

I was thinking since we’re generating $ \binom{n}{k}$ combinations that there might be a better algorithm with a better running time since $ \binom{n}{k}=O(n^2)$ or maybe my algorithm is wasteful and there is a better way? or my analysis in fact is not correct? Which one is it?