combinations

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>>ans;
        vector<int>path;
        dfs(1,0,n,k,path,ans);
        return ans;
    }
    void dfs(int cur,int cnt,int n,int k,vector<int>&path,vector<vector<int>>&ans)
    {
        if(cnt==k)
        {
            ans.push_back(path);
            return;
        }
        if(cur>n)return;
        path.push_back(cur);
        dfs(cur+1,cnt+1,n,k,path,ans);
        path.pop_back();
        dfs(cur+1,cnt,n,k,path,ans);
    }
};