Medium

题目描述

给定两个整数 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 <= n <= 20
  • 1 <= k <= n

解题思路

这是一道典型的回溯算法题目，需要找出所有可能的组合。

解题思路：

  1. 回溯算法：使用深度优先搜索（DFS）来生成所有可能的组合。从数字1开始，每次选择一个数字加入当前组合，然后递归处理剩余的位置。
  2. 关键点：
    • 为了避免重复，我们需要保证选择的数字是递增的
    • 使用start参数来控制下一个可选择的最小数字
    • 当组合长度达到k时，将当前组合加入结果

优化策略：

  • 剪枝优化：当剩余数字不足以完成组合时，提前结束递归
  • 具体来说，如果剩余需要选择的数字个数 > 剩余可选择的数字个数，就可以剪枝

算法步骤：

  1. 定义递归函数，参数包括当前位置、当前组合、结果集
  2. 递归终止条件：当前组合长度等于k
  3. 遍历从start到n的所有数字，选择当前数字并递归
  4. 回溯：移除最后添加的数字，尝试下一个选择

这种方法时间复杂度为O(C(n,k))，空间复杂度为O(k)（递归栈深度）。

代码实现

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(n, k, 1, path, result);
        return result;
    }
    
private:
    void backtrack(int n, int k, int start, vector<int>& path, vector<vector<int>>& result) {
        // 剪枝：如果剩余数字不够完成组合，直接返回
        if (path.size() + (n - start + 1) < k) {
            return;
        }
        
        // 递归终止条件
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        
        // 遍历可选择的数字
        for (int i = start; i <= n; i++) {
            path.push_back(i);
            backtrack(n, k, i + 1, path, result);
            path.pop_back();
        }
    }
};

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        path = []
        
        def backtrack(start):
            # 剪枝：如果剩余数字不够完成组合，直接返回
            if len(path) + (n - start + 1) < k:
                return
            
            # 递归终止条件
            if len(path) == k:
                result.append(path[:])  # 注意要复制路径
                return
            
            # 遍历可选择的数字
            for i in range(start, n + 1):
                path.append(i)
                backtrack(i + 1)
                path.pop()
        
        backtrack(1)
        return result

public class Solution {
    public IList<IList<int>> Combine(int n, int k) {
        IList<IList<int>> result = new List<IList<int>>();
        IList<int> path = new List<int>();
        Backtrack(n, k, 1, path, result);
        return result;
    }
    
    private void Backtrack(int n, int k, int start, IList<int> path, IList<IList<int>> result) {
        // 剪枝：如果剩余数字不够完成组合，直接返回
        if (path.Count + (n - start + 1) < k) {
            return;
        }
        
        // 递归终止条件
        if (path.Count == k) {
            result.Add(new List<int>(path));
            return;
        }
        
        // 遍历可选择的数字
        for (int i = start; i <= n; i++) {
            path.Add(i);
            Backtrack(n, k, i + 1, path, result);
            path.RemoveAt(path.Count - 1);
        }
    }
}

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const result = [];
    
    function backtrack(start, path) {
        if (path.length === k) {
            result.push([...path]);
            return;
        }
        
        for (let i = start; i <= n; i++) {
            path.push(i);
            backtrack(i + 1, path);
            path.pop();
        }
    }
    
    backtrack(1, []);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(C(n,k)) - 需要生成所有可能的组合，组合数为C(n,k)
空间复杂度O(k) - 递归栈的深度为k，path数组最大长度为k

相关题目