当前位置：首页 > news >正文

leetcode题解77：组合（回溯算法的门面）

news 2025/6/30 12:20:12

一、题目内容

题目要求返回范围 [1, n] 中所有可能的 k 个数的组合。

二、题目分析

（一）输入和输出

输入：两个整数 n 和 k。输出：范围 [1, n] 中所有可能 k的个数的组合。

（二）递归函数 backtracking 的逻辑

基本情况：如果当前路径 path 的大小等于 k，说明已经找到了一个满足条件的组合，将其加入结果 result 中，然后返回。

递归逻辑：

从 startindex 开始，依次将当前数字 i 加入路径 path 中。

递归地调用 backtracking 函数，将 startindex 设置为 i + 1，表示下一个数字从 i + 1 开始。

在递归返回后，将当前数字 i 从路径 path 中移除，以便尝试下一个数字。

（三）解题思路

基本情况：如果当前路径 path 的大小等于 k，说明已经找到了一个满足条件的组合，将其加入结果 result 中，然后返回。

递归逻辑：

从 startindex 开始，依次将当前数字 i 加入路径 path 中。

递归地调用 backtracking 函数，将 startindex 设置为 i + 1，表示下一个数字从 i + 1 开始。

在递归返回后，将当前数字 i 从路径 path 中移除，以便尝试下一个数字。

递归返回：递归返回时，返回当前节点。这一步确保了递归调用的正确性，使得每次递归返回后，当前节点的状态被正确恢复，不会影响后续的递归调用。

三、解题要点

（一）组合的定义

组合是从 n 个不同元素中，任取 k（k≤n）个元素并成一组，不考虑其顺序。

（二）解题思路

基本情况：如果当前路径 path 的大小等于 k，说明已经找到了一个满足条件的组合，将其加入结果 result 中，然后返回。

递归逻辑：

从 startindex 开始，依次将当前数字 i 加入路径 path 中。

递归地调用 backtracking 函数，将 startindex 设置为 i + 1，表示下一个数字从 i + 1 开始。

在递归返回，后将当前数字 i 从路径 path 中移除，以便尝试下一个数字。

四、代码解答

class Solution {
public:vector<int>path;vector<vector<int>>result;void backtracking(int n,int k,int startindex ){if(path.size()==k){result.push_back(path);return ;}for(int i=startindex;i<=n;i++){path.push_back(i);backtracking(n,k,i+1);path.pop_back();}}vector<vector<int>> combine(int n, int k) {backtracking(n,k,1);return result;}
};

五、详细注释

（一）递归函数 backtracking

基本情况：如果当前路径 path 的大小等于 k，说明已经找到了一个满足条件的组合，将其加入结果 result 中，然后返回。

递归逻辑：从 startindex 开始，依次将当前数字 i 加入路径 path 中，递归地调用 backtracking 函数，将 startindex 设置为 i + 1，表示下一个数字从 i + 1 开始。在递归返回后，将当前数字 i 从路径 path 中移除，以便尝试下一个数字。

返回值：无返回值，结果存储在 result 中。

（二）成员变量 path 和 result

path 用于当前存储路径，result 用于存储所有满足条件的组合。

六、递归和回溯的详细解释

（一）递归

递归是一种函数调用自身的方法，用于解决复杂问题。在本题中，递归用于逐层遍历每个数字，根据组合的定义，从 startindex 开始，依次将当前数字加入路径 path 中，递归地调用 backtracking 函数，将 startindex 设置为 i + 1，表示下一个数字从 i + 1 开始。递归的核心思想是将问题分解为更小的子问题，通过解决子问题来解决原问题。