依次枚举长度为k的数组每一位可以填哪些数字

写法一

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> combine(int n, int k) {
    dfs(0,1,n,k);
    return res;
    }
   void dfs(int u,int s,int n,int k)//依次枚举长度为k的数组每一位应该填什么
   {
       if(u==k)
       {
           res.push_back(path);
           return;
       }
       for(int i=s;i<=n;i++)//递增的顺序填入
       {
           path.push_back(i);
           dfs(u+1,i+1,n,k);//当前填的是i，下一位最少从i+1开始考虑
           path.pop_back();//回溯
       }
   }
};

写法二

class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> combine(int n, int k) {
    vector<int> path(k,0);
    dfs(0,1,n,k,path);
    return res;
    }
   void dfs(int u,int s,int n,int k,vector<int>& path)//依次枚举长度为k的数组每一位应该填什么
   {
       if(u==k)
       {
           res.push_back(path);
           return;
       }
       for(int i=s;i<=n;i++)//递增的顺序填入
       {
           path[u]=i;
           dfs(u+1,i+1,n,k,path);//当前填的是i，下一位最少从i+1开始考虑
       }
   }
};

依次枚举1-n的每个数字选还是不选

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combine(int n, int k) {
    dfs(1,0,n,k);
    return res;
    }
    void dfs(int u,int s,int n,int k)//依次枚举1-n的n个数选还是不选
                                     //u表示正在考虑u这个数字选还是不选
    {
        if(s==k)//已经选够k个数
        {
            res.push_back(path);
            return;
        }
        if(u>n) return;
        //不选，直接考虑下一个
         dfs(u+1,s,n,k);
        //选u
        path.push_back(u);
        dfs(u+1,s+1,n,k);
        path.pop_back();
    }
};