leetcode 46 全排列

通过回溯算法,在纸上画出求解问题的树形图,想清递归结构考虑如何剪枝。

做题的时候,建议 先画树形图 ,画图能帮助我们想清楚递归结构,想清楚如何剪枝。拿题目中的示例,想一想人是怎么做的,一般这样下来,这棵递归树都不难画出。

在画图的过程中思考清楚:

分支如何产生;
题目需要的解在哪里?是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径?
哪些搜索会产生不需要的解的?例如:产生重复是什么原因,如果在浅层就知道这个分支不能产生需要的结果,应该提前剪枝,剪枝的条件是什么,代码怎么写?

!!!#需要注意得到数组的浅复制,尤其是python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        def dfs(index,path,result):
            if index==len(nums):
                result.append(path[:])#注意这个地方,得到path数组的浅复制

                return

            for i in range(len(nums)):
                if nums[i] in path:continue
                path.append(nums[i])
                dfs(index+1,path,result)
                path.pop()#path[:]=path[:-1]

        path=[]
        result=[]
        dfs(0,path,result)
        return result

作者:liweiwei1419
链接:https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

递归,每次通过path+[]来进行复制,构造一个新的空间,不用回溯。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

       def dfs(i,path,result):
           if i==len(nums):
               result.append(path)

               return
           for j in range(len(nums)):
                if nums[j] in path:continue
                dfs(i+1,path+[nums[j]],result)

       result=[] 
       dfs(0,[],result)
       return result
全部评论

相关推荐

不要停下啊:大二打开牛客,你有机会开卷了,卷起来,去找课程学习,在牛客上看看大家面试笔试都需要会什么,岗位有什么需求就去学什么,努力的人就一定会有收获,这句话从来都经得起考验,像我现在大三了啥也不会,被迫强行考研,炼狱难度开局,啥也不会,找工作没希望了,考研有丝丝机会
点赞 评论 收藏
分享
05-20 13:59
门头沟学院 Java
米黑子米黑子:你这个成绩不争取下保研?
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:10
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务