leetcode 46. 全排列

目录

https://leetcode-cn.com/problems/permutations

简单的深度优先遍历。

尝试了 list 的 append 再 pop 和直接使用下标修改 list 的值。

看起来对结果影响很小。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        f = [False] * n
        l = []
        def dfs(i):
            if i == n:
                ans.append(l[::])
                return
            for j in range(n):
                if not f[j]:
                    l.append(nums[j])
                    f[j] = True
                    dfs(i+1)
                    f[j] = False
                    l.pop()
        dfs(0)
        return ans

执行用时 :40 ms, 在所有Python3提交中击败了88.14%的用户

内存消耗 :13.1 MB, 在所有Python3提交中击败了59.71%的用户

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        f = [False] * n
        l = [0] * n
        def dfs(i):
            if i == n:
                ans.append(l[::])
                return
            for j in range(n):
                if not f[j]:
                    l[i] = nums[j]
                    f[j] = True
                    dfs(i+1)
                    f[j] = False

        dfs(0)
        return ans

执行用时 :40 ms, 在所有Python3提交中击败了88.14%的用户

内存消耗 :13.1 MB, 在所有Python3提交中击败了59.50%的用户