LeetCode 90. 子集 II

Categories:

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

题目描述

✅ 90. 子集 II

思路分析

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

核心思路：

先对数组排序，使相同元素相邻。

通过回溯生成所有子集。

在同一层递归中，如果 nums[i] == nums[i-1] 且 i > start，跳过，避免重复子集。

复杂度分析：

时间复杂度：O(n · 2^n)，其中 n 表示数组长度。

空间复杂度：O(n)，递归栈和临时路径。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));

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

            // 选择 nums[i]
            path.add(nums[i]);
            backtrack(nums, i + 1, path, res);
            // 撤销选择
            path.remove(path.size() - 1);
        }
    }
}

import "sort"

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)

	res := make([][]int, 0)
	path := make([]int, 0)

	var dfs func(start int)
	dfs = func(start int) {
		cur := make([]int, len(path))
		copy(cur, path)
		res = append(res, cur)

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

			// 选择 nums[i]
			path = append(path, nums[i])
			dfs(i + 1)
			// 撤销选择
			path = path[:len(path)-1]
		}
	}

	dfs(0)
	return res
}

相似题目

题目	难度	考察点
78. 子集	中等	回溯
40. 组合总和 II	中等	回溯、剪枝
47. 全排列 II	中等	回溯、去重
39. 组合总和	中等	回溯
90. 子集 II	中等	回溯、去重
216. 组合总和 III	中等	回溯

本文作者: HGNULB

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