【LeetCode每日一题】——78.子集

一【题目类别】

• 数组

二【题目难度】

• 中等

三【题目编号】

• 78.子集

四【题目描述】

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

五【题目示例】

• 示例 1：

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

• 示例 2：

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

六【解题思路】

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

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

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

七【题目提示】

• $1<=nums.length<=10$
• $-10<=nums[i]<=10$
• $nums中的所有元素互不相同$

八【时间频度】

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

九【代码实现】

1. Java语言版

package Array;

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

/**
 * @Author: IronmanJay
 * @Description: 78.子集
 * @CreateTime: 2022-11-24  09:02
 */
public class p78_Subsets {

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

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs_back(0, nums, res, path);
        return res;
    }

    public static void dfs_back(int start, int[] nums, List<List<Integer>> res, List<Integer> path) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            dfs_back(i + 1, nums, res, path);
            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

2. C语言版

#include
#include

void dfs_back(int* nums, int numsSize, int** res, int* returnSize, int** returnColumnSizes, int start, int* path, int pathSize)
{
	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++)
	{
		path[pathSize++] = nums[i];
		dfs_back(nums, numsSize, res, returnSize, returnColumnSizes, i + 1, path, pathSize);
		pathSize--;
	}
}

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
	*returnSize = 0;
	*returnColumnSizes = (int*)malloc(sizeof(int) * 10001);
	int** res = (int**)malloc(sizeof(int*) * 10001);
	int* path = (int*)malloc(sizeof(int) * numsSize);
	dfs_back(nums, numsSize, res, returnSize, returnColumnSizes, 0, path, 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

十【提交结果】

1. Java语言版
   

2. C语言版