golang算法回溯

devtools/2025/3/16 7:49:39/

字符集回溯

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:
在这里插入图片描述

输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2:

输入:digits = “”
输出:[]
示例 3:

输入:digits = “2”
输出:[“a”,“b”,“c”]

提示:

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

func letterCombinations(digits string) []string {mappings:=[]string{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}n:=len(digits)ans:=[]string{}if n==0{return []string{}}var dfs func(i int)path:=make([]byte,n,n)dfs=func(i int){if i==n{ans=append(ans,string(path))return}for _,v:=range mappings[digits[i]-'0']{path[i]=byte(v)dfs(i+1)}}dfs(0)return ans
}

78. 子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:

输入:nums = [0]
输出:[[],[0]]

提示:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

选或者不选

func subsets(nums []int) [][]int {var dfs func(i int)ans:=[][]int{}arr:=[]int{}n:=len(nums)dfs=func(i int){if i==n{ans=append(ans,slices.Clone(arr))return}dfs(i+1)arr=append(arr,nums[i])dfs(i+1)arr=arr[:len(arr)-1]}dfs(0)return ans
}

枚举数字

func subsets(nums []int) [][]int {n:=len(nums)ans:=make([][]int,0,1<<n)path:=make([]int,0,n)var dfs func(int)dfs=func(i int){ans=append(ans,slices.Clone(path))for j:=i;j<n;j++{path=append(path,nums[j])dfs(j+1)path=path[:len(path)-1]}}dfs(0)return ans
}

二进制枚举

根据 从集合论到位运算,常见位运算技巧分类总结 中的「枚举子集」的技巧,可以只用简单的循环枚举所有子集。

func subsets(nums []int) [][]int {ans:=make([][]int,1<<len(nums))for i:=range ans{for j,x:=range nums{if i>>j&1==1{ans[i]=append(ans[i],x)}}}return ans
}

131. 分割回文串

给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1:

输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2:

输入:s = “a”
输出:[[“a”]]

提示:

1 <= s.length <= 16
s 仅由小写英文字母组成

枚举子串结束位置

func isHuiWen(s string)bool{for i,j:=0,len(s)-1;i<=j;i,j=i+1,j-1{if s[i]!=s[j]{return false}}return true
}
func partition(s string) [][]string {var dfs func(i int)n:=len(s)path:=[]string{}ans:=[][]string{}dfs=func(i int){if i==n{ans=append(ans,slices.Clone(path))return}for j:=i;j<n;j++{if isHuiWen(s[i:j+1]){path=append(path,s[i:j+1])dfs(j+1)path=path[:len(path)-1]}}}dfs(0)return ans
}

输入的视角(逗号选或不选)🪝

假设每对相邻字符之间有个逗号,那么就看每个逗号是选还是不选。

也可以理解成:是否要把 s[i] 当成分割出的子串的最后一个字符。注意 s[n−1] 一定是最后一个字符,一定要选。

func isPalindrome(s string, left, right int) bool {for left < right {if s[left] != s[right] {return false}left++right--}return true
}func partition(s string) (ans [][]string) {n := len(s)path := []string{}// 考虑 i 后面的逗号怎么选// start 表示当前这段回文子串的开始位置var dfs func(int, int)dfs = func(i, start int) {if i == n { // s 分割完毕ans = append(ans, slices.Clone(path))return}// 不选 i 和 i+1 之间的逗号(i=n-1 时一定要选)if i < n-1 {// 考虑 i+1 后面的逗号怎么选dfs(i+1, start)}// 选 i 和 i+1 之间的逗号(把 s[i] 作为子串的最后一个字符)if isPalindrome(s, start, i) {path = append(path, s[start:i+1])// 考虑 i+1 后面的逗号怎么选// start=i+1 表示下一个子串从 i+1 开始dfs(i+1, i+1)path = path[:len(path)-1] // 恢复现场}}dfs(0, 0)return
}

组合型回溯+剪枝

77. 组合

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

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

示例 1:

输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2:

输入:n = 1, k = 1
输出:[[1]]

提示:

1 <= n <= 20
1 <= k <= n

枚举下一个数选哪个

func combine(n int, k int) [][]int {var dfs func(i int)ans:=[][]int{}path:=[]int{}dfs=func(i int){path_len:=len(path)if path_len==k{ans=append(ans,slices.Clone(path))return}for j:=i;j>=k-path_len;j--{path=append(path,j)dfs(j-1)path=path[:len(path)-1]}}dfs(n)return ans
}

选或不选🪝

func combine(n, k int) (ans [][]int) {path := []int{}var dfs func(int)dfs = func(i int) {d := k - len(path) // 还要选 d 个数if d == 0 { // 选好了ans = append(ans, append([]int(nil), path...))return}// 如果 i > d,可以不选 iif i > d {dfs(i - 1)}// 选 ipath = append(path, i)dfs(i - 1)path = path[:len(path)-1] // 恢复现场}dfs(n)return
}

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:只使用数字19
每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。示例 1:输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。提示:2 <= k <= 9
1 <= n <= 60
func combinationSum3(k int, n int) [][]int {ans:=[][]int{}path:=[]int{}var dfs func(i,sum int)dfs=func(i,sum int){d:=k-len(path)if sum<0||sum>((i*2-d+1)*d)/2{return}if d==0{ans=append(ans,slices.Clone(path))return}for j:=i;j>=d;j--{path=append(path,j)dfs(j-1,sum-j)path=path[:len(path)-1]}}dfs(9,n)return ans
}

选或不选🪝

func combinationSum3(k, n int) (ans [][]int) {path := []int{}var dfs func(int, int)dfs = func(i, t int) {d := k - len(path) // 还要选 d 个数if t < 0 || t > (i*2-d+1)*d/2 { // 剪枝return}if d == 0 { // 找到一个合法组合ans = append(ans, slices.Clone(path))return}// 不选 iif i > d {dfs(i-1, t)}// 选 ipath = append(path, i)dfs(i-1, t-i)path = path[:len(path)-1]}dfs(9, n)return
}

22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2:

输入:n = 1
输出:[“()”]

提示:

1 <= n <= 8

func generateParenthesis(n int) []string {m:=n*2ans:=[]string{}path:=make([]byte,m)var dfs func(i,open int)dfs=func(i,open int){if i==m{ans=append(ans,string(path))return}if open<n{path[i]='('dfs(i+1,open+1)}if i-open<open{path[i]=')'dfs(i+1,open)}}dfs(0,0)return ans
}

枚举下一个左括号的位置🪝

func generateParenthesis(n int) []string {path:=[]int{}// 记录左括号的下标// i = 目前填了多少个括号// balance = 左括号个数 - 右括号个数var dfs  func(int,int)ans:=[]string{}dfs=func(i,balance int){if len(path)==n{s:=bytes.Repeat([]byte{')'},n*2)for _,j:=range path{s[j]='('}ans=append(ans,string(s))return}// 枚举填 close=0,1,2,...,balance 个右括号for close := range balance + 1 {// 先填 close 个右括号,然后填 1 个左括号,记录左括号的下标 i+closepath=append(path,i+close)dfs(i+close+1,balance-close+1)path=path[:len(path)-1]}}  dfs(0,0)return ans
}

排列型

46. 全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]
示例 3:

输入:nums = [1]
输出:[[1]]

提示:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

func permute(nums []int) [][]int {n:=len(nums)path:=make([]int,n)onPath:=make([]bool,n)ans:=[][]int{}var dfs func(int)dfs=func(i int){if i==n{ans=append(ans,slices.Clone(path))return}for j,on:=range onPath{if !on{path[i]=nums[j]onPath[j]=truedfs(i+1)onPath[j]=false}}}dfs(0)return ans
}

51. N 皇后

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例 1:

在这里插入图片描述

输入:n = 4
输出:[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:

输入:n = 1
输出:[[“Q”]]

提示:

1 <= n <= 9

func solveNQueens(n int) [][]string {queens:=make([]int,n)col:=make([]bool,n)diag1:=make([]bool,n*2-1)diag2:=make([]bool,n*2-1)ans:=[][]string{}var dfs func(int)dfs=func(r int){if r==n{board:=make([]string,n)for i,c:=range queens{board[i]=strings.Repeat(".",c)+"Q"+strings.Repeat(".",n-c-1)}ans=append(ans,board)return}//在(r,c)放皇后for c,ok:=range col{rc:=r-c+n-1if !ok&&!diag1[r+c]&&!diag2[rc]{//判断是否能放queens[r]=ccol[c],diag1[r+c],diag2[rc]=true,true,true//占用了c和两条对角线dfs(r+1)col[c],diag1[r+c],diag2[rc]=false,false,false//恢复现场}}}dfs(0)return ans
}

http://www.ppmy.cn/devtools/167497.html

相关文章

【2025】基于python+django的驾校招生培训管理系统(源码、万字文档、图文修改、调试答疑)

课题功能结构图如下&#xff1a; 驾校招生培训管理系统设计 一、课题背景 随着机动车保有量的不断增加&#xff0c;人们对驾驶技能的需求也日益增长。驾校作为驾驶培训的主要机构&#xff0c;面临着激烈的市场竞争和学员需求多样化等挑战。传统的驾校管理模式往往依赖于人工操作…

Certbot实现SSL免费证书自动续签(CentOS 7版 + Docker部署的nginx)

前置安装&#xff0c;可参考Certbot实现SSL免费证书自动续签&#xff08;CentOS 7 nginx/apache&#xff09; 如果是通过 Docker 运行 Nginx&#xff0c; certbot 无法直接检测到本地的 Nginx 配置。解决方案是 使用 standalone 模式 或 挂载 Webroot 方式获取 SSL 证书&…

设计模式--单例模式(Singleton)【Go】

引言 在设计模式中&#xff0c;单例模式&#xff08;Singleton Pattern&#xff09;是一种非常常见且实用的模式。它的核心思想是确保一个类只有一个实例&#xff0c;并提供一个全局访问点。这种模式在需要全局唯一对象的场景中非常有用&#xff0c;比如配置管理、日志记录、数…

浅谈AI落地之-加速训练

前言 曾在游戏世界挥洒创意&#xff0c;也曾在前端和后端的浪潮间穿梭&#xff0c;如今&#xff0c;而立的我仰望AI的璀璨星空&#xff0c;心潮澎湃&#xff0c;步履不停&#xff01;愿你我皆乘风破浪&#xff0c;逐梦星辰&#xff01; 混合精度&#xff1a; FL32是目前模型存…

MCU的工作原理:嵌入式系统的控制核心

MCU的工作原理可以概括为以下几个步骤&#xff1a; 1. 初始化 上电后&#xff0c;MCU从Flash存储器中加载程序代码&#xff0c;并初始化外设和寄存器。 2. 任务执行 根据程序逻辑&#xff0c;MCU执行数据处理、外设控制和通信等任务。通过中断系统实时响应外部事件。 3. 低…

免费高质量贴图(Textures) 网站推荐

以下是一些提供 免费或高质量贴图&#xff08;Textures&#xff09; 的网站&#xff0c;包括 PBR 贴图、HDRI 贴图、材质等&#xff0c;适用于 Three.js、Blender、Unity、Unreal Engine 等软件。 &#x1f30d; 1. Poly Haven&#xff08;https://polyhaven.com/&#xff09;⭐…

Java 8 + Tomcat 9.0.102 的稳定环境搭建方案,适用于生产环境

一、安装 Java 8 安装 OpenJDK 8 bash sudo apt update sudo apt install openjdk-8-jdk -y 验证安装 bash java -version 应输出类似: openjdk version “1.8.0_412” OpenJDK Runtime Environment (build 1.8.0_412-8u412-ga-1~22.04-b08) OpenJDK 64-Bit Server VM (bui…

【Linux内核系列】:文件系统收尾以及软硬链接详解

&#x1f525; 本文专栏&#xff1a;Linux &#x1f338;作者主页&#xff1a;努力努力再努力wz &#x1f4aa; 今日博客励志语录&#xff1a; 世界上只有一种个人英雄主义&#xff0c;那么就是面对生活的种种失败却依然热爱着生活 内容回顾 那么在之前的学习中&#xff0c;我们…