FilesExpand file tree

 master

/

permutations.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

35 lines (30 loc) · 930 Bytes

 master

/

permutations.py

Copy path

Top

File metadata and controls

• Code
• Blame

35 lines (30 loc) · 930 Bytes

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

# Time: O(n * n!)

# Space: O(n)

#

# Given a collection of numbers, return all possible permutations.

#

# For example,

# [1,2,3] have the following permutations:

# [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

#

class Solution:

# @param num, a list of integer

# @return a list of lists of integers

def permute(self, num):

result = []

used = [False] * len(num)

self.permuteRecu(result, used, [], num)

return result

def permuteRecu(self, result, used, cur, num):

if len(cur) == len(num):

result.append(cur + [])

return

for i in xrange(len(num)):

if not used[i]:

used[i] = True

cur.append(num[i])

self.permuteRecu(result, used, cur, num)

cur.pop()

used[i] = False

if __name__ == "__main__":

print Solution().permute([1, 2, 3])