LeetCode 078 Subsets

LeetCode

<div>

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:

<pre>Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] </pre>

Example 2:

<pre>Input: nums = [0] Output: [[],[0]] </pre>

Constraints:

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

</div>

题目大意：

求所有子集

解题思路：

组合知识点

解题步骤：

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()

算法分析：

时间复杂度为<code>O(nx2ⁿ)</code>，空间复杂度O(n)