力扣回溯算法--第四十二天

前言

今天是回溯算法第一天。

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

可以解决组合问题，切割问题，子集问题，排列问题，棋盘问题

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

内容

一、组合

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

递归实现组合型枚举

  var res [][]intvar nums []int
func combine(n int, k int) [][]int {nums,res=make([]int,0,k),make([][]int,0)dfs(n,k,1)
return res}func dfs (n,k,start int){if len(nums)==k{temp:=make([]int,k)copy(temp,nums)res=append(res,temp)return}for i:=start;i<=n;i++{if n-i+1<k-len(nums){// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 tempbreak}nums=append(nums,i)dfs(n,k,i+1)nums=nums[:len(nums)-1]//从 nums 中移除最后一个数字（回溯}}

二、组合总和III

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次 

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

回溯

var res [][]int
var nums []intfunc combinationSum3(k int, n int) [][]int {
res,nums=make([][]int,0),make([]int,0,k)
dfs(k,n,1,0)
return res
}func dfs(k,n,start,sum int){if len(nums)==k{if sum==n{temp:=make([]int,k)copy(temp,nums)res=append(res,temp)}return }for i:=start;i<=9;i++{if sum+i>n||9-i+1<k-len(nums){break}nums=append(nums,i)dfs(k,n,i+1,sum+i)nums=nums[:len(nums)-1]}
}

最后

时间紧迫，关注内心，关心重要的事，不要被身外物所累。