Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example:
Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
Companies:
Google
Related Topics:
Backtracking
Similar Questions:
// OJ: https://leetcode.com/problems/combinations/
// Author: github.com/lzl124631x
// Time: O(K!)
// Space: O(K)
class Solution {
vector<vector<int>> ans;
void dfs(int n, int k, int start, vector<int> &tmp) {
if (tmp.size() == k) {
ans.push_back(tmp);
return;
}
for (int i = start, end = n - k + tmp.size(); i <= end; ++i) {
tmp.push_back(i + 1);
dfs(n, k, i + 1, tmp);
tmp.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
vector<int> tmp;
dfs(n, k, 0, tmp);
return ans;
}
};