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();
}
}
};
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)))
.