77. Combinations
1. Description
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
You may return the answer in any order.
2. Example
Example 1:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:
Input: n = 1, k = 1
Output: [[1]]
3. Constraints
- 1 <= n <= 20
- 1 <= k <= n
4. Solutions
Backtracking
Time complexity: O($C_{num}^{select}select$)
Space complexity: O(num)
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<int> selection;
_search_combinations(1, n, k, selection);
return _full_combinations;
}
private:
vector<vector<int>> _full_combinations;
void _search_combinations(const int left, const int right, const int to_select, vector<int> &m_selection) {
if (to_select == 0) {
_full_combinations.emplace_back(m_selection);
} else {
for (int i = left; i <= right - (to_select - 1); ++i) {
m_selection.push_back(i);
_search_combinations(i + 1, right, to_select - 1, m_selection);
m_selection.pop_back();
}
}
}
};