C/C++教程

回溯法 leetcode78 77 46

本文主要是介绍回溯法 leetcode78 77 46,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

回溯法

points:
1 是一个不断试错的算法
2 采用递归思想 在进入下一层后 会进行一次回溯(将该层更改的复原 方便进行别的方向的试错)

经典例题 78

看到题目如何想到回溯:
题目要求返回输入的所有子集
point1:返回子集长度分别是0,1…,len(nums) 每次运行都将层次+1
point2: 回溯的思想 在长度确定的情况下 添加元素 之后要下个层次添加元素 将上个层次添加的元素删除
point3: 递归返回空值 不返回任何元素
point4:不允许重复,直接向后遍历即可

代码:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtracking(nums,res,index,subset,length):
            if len(subset) == length:
                res.append(subset[:])
                return   #point3 返回空值
            for i in range(index,len(nums)):
                subset.append(nums[i])
                backtracking(nums,res,i+1,subset,length)#point4 向后遍历
                subset.pop() #point2 删除上次添加的元素 进入下个层次
        res = []
        for i in range(len(nums)+1): #point1 层次+1
            backtracking(nums,res,0,[],i)
        return res

经典例题77

题目要求返回整数[1,n]数内 长度为k的任意组合
point1:设置一个数组之后由于题目要求不能重复,即简单的向后遍历,删除,再遍历,经典的回溯过程。
point2:设置往后遍历的层次

代码

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtracking(nums,res,subset,k,index):
            if len(subset) == k:
                res.append(subset[:])
                return  
            for i in range(index,len(nums)):
                subset.append(nums[i])
                backtracking(nums,res,subset,k,i+1)#point1 point2
                subset.pop()#point1中的回溯 删除元素
        nums = [i for i in range(1,n+1)]
        res = []
        backtracking(nums,res,[],k,0)
        return res

经典例题46

全排列
题目要求返回给定数组的所有排列方式,可以像画树一样一个一个画下来,在使用过的数字上打上使用过的标记,挨个往里添加元素,如图所示,确定了一个元素之后往下遍历直至递归终止条件开始回溯
在这里插入图片描述

代码

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtracking(nums,res,used,temp):
            if len(temp) == len(nums):
                res.append(temp[:])
                return 
            for i in range(len(nums)):
                if used[i]:
                    used[i] = False
                    temp.append(nums[i])
                    backtracking(nums,res,used,temp)
                    temp.pop()
                    used[i] = True
        res = []
        used = [True for i in range(len(nums))]
        backtracking(nums,res,used,[])
        return res
这篇关于回溯法 leetcode78 77 46的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!