image.png
典型的dfs+回溯
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
vector<int> list;
if(n == 0) return result;
dfs(n, k, 1, result, list);
return result;
}
private:
void dfs(int n, int k, int cur, vector<vector<int>>& result, vector<int> list){
if(list.size()== k) result.push_back(list);
for(int i = cur; i <= n; i++){
list.push_back(i);
dfs(n, k, i+1, result, list);
list.pop_back();
}
}
};
