It can also be done using backtracking by maintaining a visited array.
void foo(vector<vector<int> > &s,vector<int> &data,int go,int k,vector<int> &vis,int tot)
{
vis[go]=1;
data.push_back(go);
if(data.size()==k)
{
s.push_back(data);
vis[go]=0;
data.pop_back();
return;
}
for(int i=go+1;i<=tot;++i)
{
if(!vis[i])
{
foo(s,data,i,k,vis,tot);
}
}
vis[go]=0;
data.pop_back();
}
vector<vector<int> > Solution::combine(int n, int k) {
vector<int> data;
vector<int> vis(n+1,0);
vector<vector<int> > sol;
for(int i=1;i<=n;++i)
{
for(int i=1;i<=n;++i) vis[i]=0;
foo(sol,data,i,k,vis,n);
}
return sol;
}