[LeetCode] Challenge log 46

Posted on |
46. Permutations

DFS practice.

Algorithm1:

  1. use a stack to store current set, if len(stack) == len(nums), append stack to res
  2. choose a number from nums, append it to stack and mark it as used. DFS to the next level.

Algorithms2:

  1. use recursion to build all the possible set simultaneously.

Given a collection of distinct integers, return all possible permutations.

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# standard dfs
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def dfs(st, nums):
            if len(st) == len(nums): res.append(st)
            for i in range(len(nums)):
                if nums[i] is None: continue
                temp = nums[i]
                nums[i] = None
                dfs(st + [temp], nums)
                nums[i] = temp
        res = []
        dfs([], nums)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# use recursion to build all the possible set simultaneously.
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        if n == 0 : 
            return []
        elif n == 1:
            return [nums]
        else:
            res = []
            for i in range(n):
                 res += [[nums[i]] + x for x in self.permute(nums[:i] + nums[i+1:])]
            return res
0%