LeetCode LCR 081. 组合总和

Categories:

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

题目描述

✅ LCR 081. 组合总和

思路分析

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

核心思路：

先对 candidates 排序，为后续剪枝做准备。

定义递归函数，参数为 start（当前可选起始下标）和 remain（剩余目标值）。

终止条件：remain == 0 时，将当前路径加入结果集。

枚举：从 start 开始枚举每个候选数 candidates[i]：

若 candidates[i] > remain，由于数组已排序，后续元素更大，直接 break 剪枝。

否则将 candidates[i] 加入路径，递归时传 i（而非 i+1），允许重复选当前元素。

递归返回后弹出路径末尾元素（回溯）。

与普通组合的关键区别：普通组合递归传 i+1，每个元素至多选一次；本题递归传 i，同一元素可重复使用。

复杂度分析：

时间复杂度：O(n × 2^(target/min))，其中 n 为候选数组长度，min 为候选数组中最小值

空间复杂度：O(target/min)，递归栈深度

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        // 排序，便于剪枝
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(
            int[] candidates, int remain, int start,
            List<Integer> path, List<List<Integer>> res) {
        // 剩余为 0，找到一个合法组合
        if (remain == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            // 当前候选数已超过剩余目标，后续更大，直接剪枝
            if (candidates[i] > remain) {
                break;
            }
            path.add(candidates[i]);
            // 递归传 i 而非 i+1，允许重复选择当前元素
            backtrack(candidates, remain - candidates[i], i, path, res);
            // 回溯，移除末尾元素
            path.remove(path.size() - 1);
        }
    }
}

func combinationSum(candidates []int, target int) [][]int {
	var res [][]int
	var path []int

	// 排序，便于剪枝
	sort.Ints(candidates)

	var backtrack func(start, remain int)
	backtrack = func(start, remain int) {
		// 剩余为 0，找到一个合法组合
		if remain == 0 {
			res = append(res, append([]int{}, path...))
			return
		}
		for i := start; i < len(candidates); i++ {
			// 当前候选数已超过剩余目标，后续更大，直接剪枝
			if candidates[i] > remain {
				break
			}
			path = append(path, candidates[i])
			// 递归传 i 而非 i+1，允许重复选择当前元素
			backtrack(i, remain-candidates[i])
			// 回溯，移除末尾元素
			path = path[:len(path)-1]
		}
	}

	backtrack(0, target)
	return res
}

相似题目

题目	难度	考察点
40. 组合总和 II	中等	回溯、去重
216. 组合总和 III	中等	回溯、组合
377. 组合总和 Ⅳ	中等	动态规划
78. 子集	中等	回溯、枚举子集
90. 子集 II	中等	回溯、有重复元素
46. 全排列	中等	回溯、全排列
77. 组合	中等	回溯、组合枚举

本文作者: HGNULB

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