Time Complexity : O(n ^ k)

Running Time: beat 75.71%

```
vector<vector<int>> combine(int n, int k) {
vector<int> combo;
vector<vector<int>> res;
if ( k <= 0 || n < 1 || n < k) return res;
DFS(1, n, k, combo, res);
return res;
}
void DFS(int pos, int n, int k, vector<int>& combo, vector<vector<int>>& res) {
if (combo.size() > k) return;
if (combo.size() == k) {
res.push_back(combo);
return;
}
for (int i = pos; i <= n; i++) {
combo.push_back(i);
DFS(i + 1, n, k, combo, res);
combo.pop_back();
}
}
```

Typical DFS + backtracking.

lots of people are using DP on this problem. I don't think DP is good for this kind of combinatorial search. I don't see traditional DFS can produce duplicate subproblem, which is key point for DP application.