77. 组合（力扣LeetCode）

文章目录

• 77. 组合
• • 题目描述
  • 回溯算法
  • ���合问题的剪枝操作

    77. 组合

    题目描述

    给定两个整数 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 public: // 组合的主要公共接口，返回所有可能的k个数的组合 vector // 从数字1开始进行回溯搜索 backtracking(n, k, 1); // 返回搜索结果 return result; }private: // 用来存放最终的组合结果 vector // 如果当前路径的长度等于k，说明找到了一个长度为k的组合 if (path.size() == k) { // 将当前路径加入到结果集中 result.push_back(path); // 返回上一层递归 return; } // 从startindex开始，尝试所有可能的下一个元素 for (int i = startindex; i // 将当前元素加入到当前路径 path.push_back(i); // 递归调用backtracking，注意下一次递归开始的索引是i+1，这样就不会有重复的组合 backtracking(n, k, i + 1); // 将当前元素从路径中移除，也称为回溯 path.pop_back(); } // 如果循环结束，返回上一层递归 return; }};public: // combine函数用于获取所有可能的组合 vector // 从数字1开始递归回溯搜索 backtracking(n, k, 1); // 返回最终的结果列表 return result; }private: // result用于存储所有的组合 vector // 如果当前路径中的数字数量已经达到k个，则将当前路径保存到结果列表中 if (path.size() == k) { result.push_back(path); return; } // 进行循环，尝试所有可能的数 // 注意：这里使用了优化，减少了搜索的范围，避免了不必要的递归 // n - (k - path.size()) + 1是剪枝后的上界 for (int i = startindex; i // 将当前数字i加入到当前组合路径中 path.push_back(i); // 递归调用backtracking，进行下一层搜索，下一次搜索从i+1开始 backtracking(n, k, i + 1); // 回溯，移除当前路径中的最后一个数字，回到上一步，尝试其它可能的数字 path.pop_back(); } // 当循环结束，返回上一层递归 return; }};