回溯算法--LC46.全排列

zeronose

已于 2022-04-17 21:53:09 修改

阅读量133

点赞数

分类专栏： leetcode 文章标签： leetcode 回溯法

于 2022-04-17 16:51:06 首次发布

本文链接：https://blog.csdn.net/zeronose/article/details/124232189

版权

leetcode 专栏收录该内容

75 篇文章

订阅专栏

本文介绍了如何使用Python实现列表全排列的递归算法，并对比了两种版本，一种适用于无重复元素，另一种通过`used`数组处理重复元素。讲解了回溯法在解决组合问题中的应用和优化技巧。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

在这里插入图片描述

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        path = list()
        result = list()
        def backtracking(nums):
            if len(path) == len(nums):
                result.append(path[:])
                return
            for i in range(0, len(nums)):
            	# 这种方式只适合无重复的数组，还是加个used数组好用，适合无重复/重复的数组
                if nums[i] in path:
                    continue
                path.append(nums[i])
                backtracking(nums)
                path.pop()
        backtracking(nums)
        return result

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        path = list()
        result = list()
        used = [0 for _ in range(len(nums))]
        def backtracking(nums):
            if len(path) == len(nums):
                result.append(path[:])
                return
            for i in range(0, len(nums)):
                if used[i]:
                    continue
                used[i] = 1
                path.append(nums[i])
                backtracking(nums)
                path.pop()
                used[i] = 0
        backtracking(nums)
        return result