组合

给定两个整数 n 和 k 返回范围 [1, n]中所有可能的 k 个数的组合。 你可以按任何顺序返回答案。

示例 1： 输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2： 输入：n = 1, k = 1 输出：[[1]]

这种题目思路其实很简单，考虑两种情况：

1. 对于当前元素判断，选或者不选，
2. 枚举选哪个元素。

C++

class Solution {
public:
  vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    vector<int> path;

    function<void(int)> dfs=[&](int i){
      if(i>n ) return ;
      if(path.size()==k){
        ans.emplace_back(path);
        return ;
      }
      if(i>n ) return ;

      //不选
      dfs(i+1);

      //下面是选的情况
      path.push_back(i);
      dfs(i+1);
      path.pop_back();//注意恢复现场
    };
    dfs(1);
    return ans;
  }
};

C++

class Solution {
public:
  vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    vector<int> path;

    function<void(int)> dfs=[&](int i){
      if(i>n ) return ;
      if(path.size()==k){
        ans.emplace_back(path);
        return ;
      }
      if(i>n ) return ;
   
      //下面给出另一种枚举选哪个,
      for (int j = i; j<= n; j++) {
        path.push_back(j);
        dfs(j+1);
        path.pop_back(); // 恢复现场
      }
    };
    dfs(1);
    return ans;
  }
};

注意

第13行的判断不能移到前面去，否则会丢失解，因为从后续递归来看，会先把答案记录进path之后，才会递归到到 i+1，再判断是否出界的情况。

更新日志

2024/12/13 13:22

查看所有更新日志

• 24fac-prepare interview于 2024/12/13