46. Permutations

2019-04-24

46. Permutations

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]
]

Code：

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """

        return nums and [p[:i] + [nums[0]] + p[i:]
                        for p in self.permute(nums[1:])
                        for i in range(len(nums))] or [[]]
1
2
3
4
5
6
7
8
9
10
11
12
# DFS
def permute(self, nums):p
    res = []
    self.dfs(nums, [], res)
    return res

def dfs(self, nums, path, res):
    if not nums:
        res.append(path)
        # return # backtracking
    for i in xrange(len(nums)):
        self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
-->