-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path78_subsets.py
46 lines (35 loc) · 1013 Bytes
/
78_subsets.py
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
41
42
43
44
45
46
"""
---
title: Subsets
number: 78
difficulty: medium
tags: ['Array','Backtracking','Bit Manipulation']
url: https://leetcode.com/problems/subsets/
solved: true
---
"""
from typing import List
"""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.
"""
### Backtracking - recursive
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
subset = []
def recursive(index: int):
print("sa")
if index >= len(nums):
res.append(subset.copy())
return
# include current item
subset.append(nums[index])
recursive(index+1)
# not include current item
subset.pop()
recursive(index+1)
recursive(0)
return res
if __name__ == '__main__':
nums = [1,2,3]
print(Solution().subsets(nums))