# My shortest c++ solution,using dfs

• my idea is using backtracking ,every time I push a number into vector,then I push a bigger one into it;
then i pop the latest one,and push a another bigger one...
and if I has push k number into vector,I push this into result;

this solution take 24 ms.

``````class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<vector<int> >res;
if(n<k)return res;
vector<int> temp(0,k);
combine(res,temp,0,0,n,k);
return res;
}

void combine(vector<vector<int> > &res,vector<int> &temp,int start,int num,int n ,int k){
if(num==k){
res.push_back(temp);
return;
}
for(int i = start;i<n;i++){
temp.push_back(i+1);
combine(res,temp,i+1,num+1,n,k);
temp.pop_back();
}
}
};``````

• How about this, avoid calling `push_back()` and `pop_back()` too often.

``````class Solution {
public:
vector<vector<int> > combine(int n, int k) {
v.resize(k);
dfs(1, n, k);
return r;
}
private:
vector<vector<int> > r;
vector<int> v;
void dfs(int i, int n, int k) {
while (i <= n) {
v[v.size() - k] = i++;
if (k > 1)
dfs(i, n, k - 1);
else
r.push_back(v);
}
}
};``````

• according the backtracking idea!

• nice solution. Maybe v.size() can be change to new variable klen while klen=v.size().

• Improved the dfs method, using pruning when dfs. takes 8 ms. `i <= (n-k+1)` replace `i<=n`.

Because our dfs result is a sorted array.

if n = 5, k = 3;
we select i = 1 at first, v =[1, X, X], X means need to fill using dfs.

then we iterate i, i = 2, v = [2, X, X]
i = 3, v = [3, X, X].

now we need stop to search. if v= [4, X, X], we can't find 2 number greater than 4, and in the range [1, 5];

``````class Solution {
public:
vector<vector<int> > combine(int n, int k) {
// dfs method
if(k == 0 || n == 0 || n<k)
return result;
v.resize(k);
combinecore(1, n, k);
return result;
}

void combinecore(int startnum, int n, int k) {
int i = startnum;
while(i<=(n-k+1)) {
v[v.size()-k] = i;
i++;
if(k>1)
combinecore(i, n, k-1);
else
result.push_back(v);
}
}
private:
vector<int> v;
vector<vector<int> > result;
};
``````

• why "vector<int> temp(0, k)" ? but not "vector<int> temp".

• Nice code , very good!!!!!

• Thank you for sharing your solution. This is my java version.

``````public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
backtrack(res,1,n,k,k,new ArrayList<Integer>(k));
return res;
}

private void backtrack(List<List<Integer>> res, int i, int n, int k, int cap, List<Integer> list) {
while(i<=n) {
List<Integer> copy = new ArrayList<Integer>(list);
if(k>1)
backtrack(res,i,n,k-1,cap,copy);
else {