What's time complexity of this algorithm for finding all combinations?

Question

Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example, If n = 4 and k = 2, a solution is:

[    [2, 4],    [3, 4],    [2, 3],    [1, 2],    [1, 3],    [1, 4], ] 

---

Personally I think,
time complexity = O(n^k), n and k are input.

---

Thank you for all help.
Finally, the time complexity = O(C(n,k) * k) = O((n!/(k! * (n - k)!)) * k), n and k is input,
Since, each time when we get a combination, we need copy subList list to one_rest, which is O(k), there is C(n, k) * k.

---

C++

#include <vector> using namespace std;  class Solution { public:     vector<vector<int> > combine(int n, int k) {         vector<vector<int>> list;          // Input validation.         if (n < k) return list;          int start = 1;         vector<int> subList;         helper(n, k, start, list, subList);          return list;     }      void helper(int n, int k, int start,                  vector<vector<int>> &list, vector<int> &subList) {         // Base case.         if (subList.size() == k) {             vector<int> one_rest(subList);             list.push_back(one_rest);             return;         }         if (start > n) return;          for (int i = start; i <= n; i ++) {             // Have a try.             subList.push_back(i);              // Do recursion.             helper(n, k, i + 1, list, subList);              // Roll back.             subList.pop_back();         }     } }; 

Answer 1

The complexity is O(C(n,k)) which is O(n choose k).

This ends up being equivalent to O(min(n^k, n^(n-k))).

Answer 2

Since you are using lists, push_back and pop_back are O(1) operations. Also, you end up generating a valid combination exactly once. Thus, the complexity is O(n choose k).