力扣--深度优先算法/回溯算法77.组合

回溯算法是深度优先算法的一种特殊情况。

思路分析：

1. 深度优先搜索 (DFS)： 通过递归实现，从起始数字开始遍历，逐步构建可能的组合。
2. 递归函数 dfs：
   • 接收参数：result 为最终结果集，smallresult 为当前正在生成的组合，n 为总数字范围，k 为组合长度，start 为当前选择的起始位置。
   • 逐个尝试可能的数字，构建临时结果集。
   • 如果临时结果集大小等于目标长度 k，将其加入最终结果集。
   • 否则，继续递归生成组合，注意起始位置更新为 i+1，避免重复选择元素。
   • 回溯过程中，撤销选择，继续尝试其他可能的组合。
3. 主函数：
   • 创建空的结果集 result 和临时结果集 smallresult。
   • 调用深度优先搜索函数 dfs，从数字 1 开始生成组合。
   • 返回最终结果。

class Solution {
    // 定义深度优先搜索函数，用于生成组合
    void dfs(vectorint>>& result, vector<int>& smallresult, int n, int k, int start) {
        // 遍历当前可能的组合元素
        for (int i = start; i <= n; i++) {
            // 将当前元素加入临时结果集
            smallresult.push_back(i);
 
            // 如果临时结果集大小达到目标值 k，将其加入最终结果集
            if (smallresult.size() == k)
                result.push_back(smallresult);
            // 否则，继续递归生成组合，注意起始位置更新为 i+1，避免重复选择元素
            else
                dfs(result, smallresult, n, k, i + 1);
 
            // 回溯，撤销选择，继续尝试其他可能的组合
            smallresult.pop_back();
        }
        return;
    }
 
public:
    // 主函数，生成给定范围 [1, n] 中长度为 k 的所有组合
    vectorint>> combine(int n, int k) {
        // 存储最终结果的二维数组
        vectorint>> result;
        
        // 存储当前正在生成的组合的临时结果
        vector<int> smallresult;
 
        // 调用深度优先搜索函数，从数字 1 开始生成组合
        dfs(result, smallresult, n, k, 1);
 
        // 返回最终结果
        return result;
    }
};