46全排列

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

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

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

法一: 自己的代码

思路: 很基本的回溯算法，没有剪枝条件，r中每次传递的都是去掉已经用过的数，

class Solution:
    def permute(self, nums):
        resluts = []
        l = len(nums)
        # 注意这里的nums如果不初始化的话，要放在a的前边，否则报错.
        def backtrack(a=[], nums=nums):
            # 深度优先遍历，即回溯终止的条件
            if len(a) == l:
                resluts.append(a)
                return
            for j,i in enumerate(nums):
                # 每次回溯前，都将该数删除，为了下次回溯for循环的时候不再用
                # 这里没有用状态重置是因为 回溯时用了r来赋值给nums，每次回溯结束后仍然是原来的状态
                r = nums.copy()
                del r[j]
                # 这里的i必须加[]
                backtrack( a+[i], r)
                # 也可以不用引入r直接生成list传递，耗时稍微短点
                # backtrack( a+[i], [k for k in nums if k != i])
        backtrack()
        return resluts
if __name__ == "__main__":
    duixiang = Solution()
    a = duixiang.permute([1,2,3])
    print(a)

View Code

class Solution: def permute(self, nums): if len(nums) == 0: return [] used = [False] * len(nums) res = [] self.__dfs(nums, 0, [], used, res) return res def __dfs(self, nums, index, pre, used, res): # 先写递归终止条件 if index == len(nums): # 这里如果不用copy()的话，pre改变的时候，res中的值也会同时改变 res.append(pre.copy()) return for i in range(len(nums)): if not used[i]: # 如果没有用过，就用它 used[i] = True pre.append(nums[i]) # 在 dfs 前后，代码是对称的 self.__dfs(nums, index + 1, pre, used, res) used[i] = False pre.pop() duixiang = Solution() a = duixiang.permute([1,2,3]) print(a) # 参考：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

相关推荐