FilesExpand file tree

 master

/

subsets.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

59 lines (45 loc) · 1.06 KB

 master

/

subsets.py

Copy path

Top

File metadata and controls

• Code
• Blame

59 lines (45 loc) · 1.06 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

47

48

49

50

51

52

53

54

55

56

57

58

59

# Given a set of distinct integers, nums, return all possible subsets.

# Note: The solution set must not contain duplicate subsets.

# For example,

# If nums = [1,2,3], a solution is:

# [

# [3],

# [1],

# [2],

# [1,2,3],

# [1,3],

# [2,3],

# [1,2],

# []

# ]

# O(2**n)

def subsets(nums):

res = []

backtrack(res, nums, [], 0)

return res

def backtrack(res, nums, stack, pos):

if pos == len(nums):

res.append(list(stack))

else:

# take nums[pos]

stack.append(nums[pos])

backtrack(res, nums, stack, pos+1)

stack.pop()

# dont take nums[pos]

backtrack(res, nums, stack, pos+1)

# simplified backtrack

# def backtrack(res, nums, cur, pos):

# if pos >= len(nums):

# res.append(cur)

# else:

# backtrack(res, nums, cur+[nums[pos]], pos+1)

# backtrack(res, nums, cur, pos+1)

# Iteratively

def subsets2(self, nums):

res = [[]]

for num in sorted(nums):

res += [item+[num] for item in res]

return res

test = [1,2,3]

print(test)

print(subsets(test))