LeetCode 78. 子集
原题链接
中等
作者:
小聂同学
,
2023-11-03 04:07:46
,
所有人可见
,
阅读 63
class Solution:
'''
Allow Element Re-select: No
Contain Element duplicated: No
Avoid Duplicate: define we can only select the number after current idx,
All decision are based on the idx
Search Order: From the current idx, enumerate which number should be add to subset
T: O(n*2^n)
Decision Tree has 2^n nodes, copy cost O(n)
S: O(n) + O(n*2^n)
Recursion Stack will be the depth of the tree, max is n
2^n substes, average lenth n/2
'''
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def backtrack(nums, idx, path) -> None:
res.append(path.copy())
for i in range(idx, len(nums)):
path.append(nums[i])
backtrack(nums, i+1, path)
path.pop()
backtrack(nums, 0, [])
return res