【LeetCode每日一题】——90.子集 II

一【题目类别】

• 数组

二【题目难度】

• 中等

三【题目编号】

• 90.子集 II

四【题目描述】

• 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
• 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

五【题目示例】

• 示例 1：

  • 输入：nums = [1,2,2]
  • 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

• 示例 2：

  • 输入：nums = [0]
  • 输出：[[],[0]]

六【解题思路】

• 本题是回溯算法（有重复）的典型应用，关于回溯问题（有重复）的处理步骤如下：

void backTracking(参数)
{
	if(终止条件)
	{
		保存结果;
		return;
	}
	for(遍历从当前位置出发的所有“路径”)
	{
		if(大于开始位置 && 当前元素和前一个元素相同)
        {
            continue;
        }
		保存“路径”节点;
		backTracking(所需参数);
		回溯处理，删除上一步保存的“路径”节点，准备进行新的递归
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 本题也是这个处理步骤，只是不需要递归终止条件的设置，因为遍历完数组也相当于结束了
• 最后返回结果即可

七【题目提示】

• $1<=nums.length<=10$
• $-10<=nums[i]<=10$

八【时间频度】

• 时间复杂度：$O(n\times 2^n)$，其中$n$为输入数组的大小，因为共$2^n$种状态，每种状态需要$O(n)$的时间来构造
• 空间复杂度：$O(n)$，其中$n$为输入数组的大小

九【代码实现】

1. Java语言版

package Array;

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

/**
 * @Author: IronmanJay
 * @Description: 90.子集 II
 * @CreateTime: 2022-11-25  09:04
 */
public class p90_SubsetsII {

    public static void main(String[] args) {
        int[] nums = {1, 2, 2};
        List<List<Integer>> res = subsetsWithDup(nums);
        System.out.println("res = " + res);
    }

    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs_back_p90_SubsetsII(nums, res, path, 0);
        return res;
    }

    public static void dfs_back_p90_SubsetsII(int[] nums, List<List<Integer>> res, List<Integer> path, int start) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            dfs_back_p90_SubsetsII(nums, res, path, i + 1);
            path.remove(path.size() - 1);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

2. C语言版

#include
#include

int compare_p90_SubsetsII(const void *a, const void *b)
{
	return *(int *)a - *(int *)b;
}

void dfs_back_p90_SubsetsII(int* nums, int numsSize, int** res, int* returnSize, int** returnColumnSizes, int* path, int pathSize, int start)
{
	res[*returnSize] = (int*)malloc(sizeof(int) * pathSize);
	memcpy(res[*returnSize], path, sizeof(int) * pathSize);
	(*returnColumnSizes)[*returnSize] = pathSize;
	(*returnSize)++;
	for (int i = start; i < numsSize; i++)
	{
		if (i > start && nums[i] == nums[i - 1])
		{
			continue;
		}
		path[pathSize++] = nums[i];
		dfs_back_p90_SubsetsII(nums, numsSize, res, returnSize, returnColumnSizes, path, pathSize, i + 1);
		pathSize--;
	}
}

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
	qsort(nums, numsSize, sizeof(int), compare_p90_SubsetsII);
	*returnSize = 0;
	*returnColumnSizes = (int*)malloc(sizeof(int) * 10001);
	int** res = (int**)malloc(sizeof(int*) * 10001);
	int* path = (int*)malloc(sizeof(int) * numsSize);
	dfs_back_p90_SubsetsII(nums, numsSize, res, returnSize, returnColumnSizes, path, 0, 0);
	return res;
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

十【提交结果】

1. Java语言版
   

2. C语言版