Q46 - Medium - 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

回溯

import copy
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.back_track(res, nums, 0)
        return res
    
    def back_track(self, res, nums, n):
        if n == len(nums):
            temp = copy.deepcopy(nums)
            res.append(temp)
        else:
            for i in range(n, len(nums)):
                nums[n], nums[i] = nums[i], nums[n]
                self.back_track(res, nums, n+1)
                nums[n], nums[i] = nums[i], nums[n]

DFS

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        visited = [0] * len(nums)
        res = []
        
        def dfs(path):
            if len(path) == len(nums):
                res.append(path)
            else:
                for i in range(len(nums)):
                    if not visited[i]:
                        visited[i] = 1
                        dfs(path + [nums[i]])
                        visited[i] = 0
        
        dfs([])
        return res