LeetCode 078 Subsets

LeetCode

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:

Input: nums = [0]
Output: [[],[0]]

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10
All the numbers of nums are *unique.

题目大意：

求所有子集

解题思路：

组合知识点

解题步骤：

N/A

注意事项：

1. 题目要求结果含空集

Python代码：

def subsets(self, nums: List[int]) -> List[List[int]]:
	if not nums:
		return []
	res = [[]]
	self.dfs(nums, 0, [], res)
	return res

def dfs(self, nums, st, path, res):
	if st == len(nums):
		return
	for i in range(st, len(nums)):
		path.append(nums[i])
		res.append(list(path))
		self.dfs(nums, i + 1, path, res)
		path.pop()

算法分析：

时间复杂度为O(nx2n)，空间复杂度O(n)