What's time complexity of this algorithm for finding all combinations?
algorithm, big-o, c++, combinations, recursion
Solution
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)`.
Problem
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(); } } }; ```