LeetCode LCR 082. 组合总和 II

Categories:

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

题目描述

✅ LCR 082. 组合总和 II

思路分析

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

核心思路：

先排序，保证相同元素相邻。

回溯时从当前位置向后选择，每个元素只能使用一次。

若当前元素与前一个相同且前一个在同层未被选择，跳过避免重复组合。

复杂度分析：

时间复杂度：O(n * 2^n)，其中 n 表示元素个数，实际取决于剪枝效果。

空间复杂度：O(n)，用于递归栈与路径存储。

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        backtrack(candidates, 0, target, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] candidates, int start, int remain,
                           List<Integer> path, List<List<Integer>> res) {
        if (remain == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > remain) {
                break;
            }

            path.add(candidates[i]);
            backtrack(candidates, i + 1, remain - candidates[i], path, res);
            path.remove(path.size() - 1);
        }
    }
}

import "sort"

func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	res := make([][]int, 0)
	path := make([]int, 0)

	var dfs func(start int, remain int)
	dfs = func(start int, remain int) {
		if remain == 0 {
			tmp := make([]int, len(path))
			copy(tmp, path)
			res = append(res, tmp)
			return
		}

		for i := start; i < len(candidates); i++ {
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}
			if candidates[i] > remain {
				break
			}

			path = append(path, candidates[i])
			dfs(i+1, remain-candidates[i])
			path = path[:len(path)-1]
		}
	}

	dfs(0, target)
	return res
}

相似题目

题目	难度	考察点
39. 组合总和	中等	回溯
77. 组合	中等	回溯
216. 组合总和 III	中等	回溯
90. 子集 II	中等	回溯
40. 组合总和 II	中等	回溯

本文作者: HGNULB

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