LeetCode LCR 080. 组合

Categories:

题目描述
思路分析
1. 解法一：回溯 + 剪枝（推荐）
相似题目

题目描述

✅ LCR 080. 组合

思路分析

解法一：回溯 + 剪枝（推荐）

核心思路：

使用回溯法，从 start 开始依次枚举每个可选数字，将其加入当前路径 path。

当 path 长度等于 k 时，将当前路径加入结果集并返回。

关键剪枝：当前位置 i 到 n 之间剩余数字不足以凑满 k - path.size() 个时，无需继续枚举，直接终止循环。剪枝条件为 i <= n - (k - path.size()) + 1。

每次递归以 i + 1 作为下一层起点，保证组合不重复、不含重复元素。

复杂度分析：

时间复杂度：O(C(n, k) × k)，其中 C(n, k) 为组合数，每个合法组合需要 O(k) 时间复制路径。

空间复杂度：O(k)，其中 k 为递归栈深度及路径数组的空间开销。

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        // 当前路径
        List<Integer> path = new ArrayList<>();
        backtrack(n, k, 1, path, res);
        return res;
    }

    private void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
        // 路径长度达到 k，记录结果
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 剪枝：剩余数字不足以填满 k 个时提前终止
        for (int i = start; i <= n - (k - path.size()) + 1; i++) {
            // 选择当前数字
            path.add(i);
            // 递归，下一层从 i+1 开始
            backtrack(n, k, i + 1, path, res);
            // 回溯，撤销选择
            path.remove(path.size() - 1);
        }
    }
}

func combine(n int, k int) [][]int {
	var res [][]int
	// 当前路径
	var path []int

	var backtrack func(start int)
	backtrack = func(start int) {
		// 路径长度达到 k，记录结果
		if len(path) == k {
			res = append(res, append([]int(nil), path...))
			return
		}

		// 剪枝：剩余数字不足以填满 k 个时提前终止
		for i := start; i <= n-(k-len(path))+1; i++ {
			// 选择当前数字
			path = append(path, i)
			// 递归，下一层从 i+1 开始
			backtrack(i + 1)
			// 回溯，撤销选择
			path = path[:len(path)-1]
		}
	}

	backtrack(1)
	return res
}

相似题目

题目	难度	考察点
39. 组合总和	中等	回溯、组合（元素可重复使用）
40. 组合总和 II	中等	回溯、组合去重
216. 组合总和 III	中等	回溯、固定长度组合
78. 子集	中等	回溯、枚举所有子集
90. 子集 II	中等	回溯、子集去重
46. 全排列	中等	回溯、排列问题
17. 电话号码的字母组合	中等	回溯、多叉树枚举

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/99345020