77. 组合 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]]

解题思路

输入：两个整数 n 和 k

输出：返回范围 [1, n] 中所有可能的 k 个数的组合

这道题属于组合型回溯问题。

回溯三问

1. 当前操作？
   • 在当前位置 i，尝试选择一个数字 j 放入 path。
   • 也就是：把数字 j（j ∈ [i, 1]）放入路径 path 中，表示“我把它选上了”。
2. 子问题？
   • 选择了数字 j 以后，需要继续选择剩余的数字，且剩余数字的最大值不能超过 j-1（因为不能重复选择）。
   • 也就是：递归调用 dfs(j-1) 继续构造剩余的组合。
3. 下一个子问题？
   • 下一步递归就从 dfs(j-1) 开始，继续往下挑选数字。
   • 这就是“往下分支”，也就是在剩下的数字里继续选。

剪枝条件

• 当剩余数字数量比 k - len(path) 小的时候就不用再尝试了，因为一定凑不到 k 个数

代码实现

python

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []     # 最终结果，保存所有组合
        path = []    # 当前的组合路径

        def dfs(i):
            # 剩余可选数字的个数必须 ≥ 剩余需要选择的数字个数
            # 剪枝：如果剩下的数字都不够填满path，就直接返回
            if i < k - len(path):
                return

            # 如果已经选够k个数了，就把当前方案加入结果
            if len(path) == k:
                ans.append(path.copy())
                return

            # 从大到小选择数字，避免重复组合（每个数字只能选一次）
            for j in range(i, 0, -1):
                path.append(j)      # 选择当前数字
                dfs(j - 1)          # 继续选择剩余的数字
                path.pop()          # 回溯，撤销选择

        dfs(n)  # 从n开始递归
        return ans

javascript

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
const combine = function(n, k) {
    ans = []
    path = []

    function dfs(i) {
        const d = k - path.length;
        if (i < d) return;

        if (path.length == k) {
            ans.push([...path]);
            return;
        }

        for (let j = i; j > 0; j--) {
            path.push(j);
            dfs(j - 1);
            path.pop();
        }
    }  
    dfs(n);
    return ans;
};

复杂度分析

时间复杂度：O(n * 2^n)

空间复杂度：O(n * 2^n)

链接

77 国际版

77 中文版