龙岗区,长沙seo网站排名,小程序代理与加盟,网易邮箱用企业邮箱账号怎么登录用于记录为期60天的算法提升过程#xff0c;今天是第27天 #x1f578;️代码随想录训练营-回溯#x1f578;️ 39. #x1f338;组合总和#x1f338;思路#xff1a;代码 40. #x1f338;组合总和 II#x1f338;思路代码#xff1a; 131. 分割回文串 39. #x…用于记录为期60天的算法提升过程今天是第27天 ️代码随想录训练营-回溯️ 39. 组合总和思路代码 40. 组合总和 II思路代码 131. 分割回文串 39. 组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同则两种组合是不同的。 对于给定的输入保证和为 target 的不同组合数少于 150 个。 思路
回溯水平遍历作为可选的路径方向竖直方向用于深度递归终止条件是子数字的和target。
代码
var( res [][] intpath []int
)
func combinationSum(nums []int, target int) [][]int {res,path make([][]int,0),make([]int,0,len(nums))sort.Ints(nums)//方便剪枝dfs(nums,0,target)return res
}
func dfs(nums[]int, start int,target int){if target 0{//触底 记录数组 反弹tmp:make([]int,len(path))copy(tmp,path)res append(res,tmp)return }for i :start;ilen(nums);i{//水平 方向if nums[i] target{ break }//剪枝提前终止path append(path,nums[i])//加入新的路径元素dfs(nums,i,target-nums[i])//往下递归path path[:len(path)-1]//不保存此次路径用于同层}
}
40. 组合总和 II 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意解集不能包含重复的组合。 思路
设置一个状态数组用来维护当前元素是否在层间被访问完毕如果是边可以重复如果是层则不能重复
代码 var(res [][]intpath []intused []bool
)func combinationSum2(nums []int, target int) [][]int {res,path make([][]int,0),make([]int,0)//used make([]bool,len(nums))//多增加一个描述每一个下标元素状态的数组sort.Ints(nums)dfs(nums,0,target)return res
}func dfs(nums []int,start int,target int){if target 0{tmp:make([]int,len(path))copy(tmp,path)res append(res,tmp)return}
//我可以在树的边上重复使用元素但不能在树的层间重复使用元素for i:start;ilen(nums);i{if nums[i]target{ break;}if i0 nums[i]nums[i-1] used[i-1] false{continue;}path append(path,nums[i])used[i] truedfs(nums,i1,target-nums[i])used[i] falsepath path[:len(path)-1]}
}
131. 分割回文串 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 思路 感觉有点难理解水平切 之后对切割完的串进行判断
//1,234 12,34 123,4 1234var (path []stringres [][]string
)func partition(s string) [][]string {path ,res make([]string,0),make([][]string ,0)dfs(s,0)return res
}func dfs(s string ,start int){if start len(s){tmp :make([]string,len(path))copy(tmp,path)res append(res,tmp)return }for i: start;i len(s);i{str :start:i1]if isPalindrome(str){path append(path,str)dfs(s,i1)path path[:len(path)-1]}}
}
func dfs(s string, start int) {if start len(s) { // satrt lentmp : make([]string, len(path))copy(tmp, path)res append(res, tmp)return }for i : start; i len(s); i {str : s[start : i1]//1,234] 12,34] 123,4], [1234]if isPalindrome(str) { // 判断切割的字符串path append(path, str)dfs(s, i1) // 寻找i1为起始位置的子串path path[:len(path)-1] // 回溯过程弹出本次已经添加的子串}}
}func isPalindrome(s string) bool {for i, j : 0, len(s)-1; i j; i, j i1, j-1 {if s[i] ! s[j] {return false}}return true
}go
