Loading... # 全排列 这题目也是一开始完全没有思路，不知道咋才能把全部的都输出一遍，感觉套for循环也不知道怎么写，后来看到答案直接恍然大悟，这其实是一个经典的回溯题，dfs+状态回溯即可完成。 值得注意的是，通过这道题还突然意识到golang的函数传递其实是值传递，实在是太久没有看相关的文章有点忘记了，这里如果res的参数类型改成非指针，就会复制一份切片的结构体过去，一般情况下这不会引发任何问题，但是一旦进行了append操作，因为涉及到了扩容，就可能会产出一个新的切片结构，而因为是值传递，从而这个新的切片结构体只在函数内作为局部变量存在，不影响外部的切片，就会导致最终的答案出现错误，这是一个需要注意的点。 ```go func permute(nums []int) [][]int { n := len(nums) res := make([][]int, 0) used := make([]bool, n) path := make([]int, 0) dfs(used, path, nums, &res) return res } func dfs(used []bool, path, nums []int, res *[][]int) { if len(path) == len(nums) { tmp := make([]int, len(path)) copy(tmp, path) *res = append(*res, tmp) return } for i := 0; i < len(nums); i++ { if used[i] { continue } used[i] = true path = append(path, nums[i]) dfs(used, path, nums, res) path = path[:len(path)-1] used[i] = false } } ``` # 组合总和 这道题主要就是思考如何去掉重复的结果，因为每个数字可以重复利用，相比于全排序这个题来说，我们可以重复利用一个数多次，但是必须要利用一个数的次数不同才属于不同的组合。 其实只需要在每一轮 dfs 中，利用一个 start 传递，并且让每一轮传给下一轮的起始点为当前遍历的 i 即可符合要求（保障了不走之前走过的路）。 ```go func combinationSum(candidates []int, target int) [][]int { res := make([][]int, 0) dfs(candidates, &res, []int{}, 0, target, 0) return res } func dfs(candidates []int, res *[][]int, curArr []int, cur, target, start int) { if cur > target { return } if cur == target { dst := make([]int, len(curArr)) copy(dst, curArr) *res = append(*res, dst) } for i := start; i < len(candidates); i++ { curArr = append(curArr, candidates[i]) dfs(candidates, res, curArr, cur+candidates[i], target, i) curArr = curArr[:len(curArr)-1] } } ``` # 复原IP地址 这道题其实一看也知道是回溯，但是问题就在于如何判断什么时候才能归入答案，中间的剪枝要怎么弄。 首先第一点我们需要把中间的答案存储在一个[]string里面，这样比较好判断刚好达到四段，然后再通过当前位移是否已经抵达字符串终点来判断是否满足IP地址要求。 剪枝可以通过前导零，转换成数字看是否大于255来进行判断。 ```go func restoreIpAddresses(s string) []string { res := []string{} dfs(s, []string{}, 0, &res) return res } func dfs(s string, cur []string, start int, res *[]string) { if len(cur) == 4 && start == len(s) { *res = append(*res, strings.Join(cur, ".")) } for i := 1; i <= 3; i++ { if start + i > len(s) { break } part := s[start:start+i] if len(part) > 1 && part[0] == '0' { break } num, err := strconv.Atoi(part) if err != nil || num > 255 { continue } dfs(s, append(cur, part), start + i, res) } } ``` # 划分为k个相等的子集 这道题主要是先得知道我们需要构造的子集和应该为多少，sum(nums) / k，如果不能整除说明无法构造，如果可以，我们可以先倒序排序 nums，然后开始回溯式DFS构造，要注意的细节比较多。 一个是如果构造成功一个子集，接着往下走，不进行回溯（废话）。 一个是回溯到最开始，子集一个元素都没塞进去，说明没有满足构造桶的元素，可以退出。 一个是构造成功了 k-1 个子集，剩下的元素肯定能构成最后一个子集，因为 $sum(nums)\mod{k} == 0$ ```go func canPartitionKSubsets(nums []int, k int) bool { sum := 0 for _, v := range nums { sum += v } if sum % k != 0 { return false } target := sum / k sort.Slice(nums, func (i, j int) bool { return nums[i] > nums[j] }) if nums[0] > target { return false } visited := make([]bool, len(nums)) return dfs(nums, visited, 0, 0, 0, target, k) } func dfs(nums []int, visited []bool, start, cur, cnt, target, k int) bool { // 如果已经构造成功 k-1 个子集，剩下的一个一定满足，因为 sum % k == 0 if cnt == k - 1 { return true } // 构造成功一个子集，从头开始重新构造，因为这里visited没有回溯所以不会重复使用 if cur == target { return dfs(nums, visited, 0, 0, cnt+1, target, k) } for i := start; i < len(nums); i++ { if visited[i] || cur + nums[i] > target { continue } visited[i] = true if dfs(nums, visited, i+1, cur+nums[i], cnt, target, k) { return true } visited[i] = false // 如果查找一圈没找到能满足条件的，说明不满足 if cur == 0 { break } } return false } ``` # 字母迷宫 这个题目也是回溯做法，但是需要注意的是这个题目需要爆搜所有的位置，属于典型题，唯一需要注意的是 visited 的标记和回溯时机应该在走完整条路径都不满足的时候回溯，而在进入节点的时候标记。 ```go var dirs = [5]int{1, 0, -1, 0, 1} func wordPuzzle(grid [][]byte, target string) bool { n := len(grid) m := len(grid[0]) visited := make([][]bool, n) for i := range visited { visited[i] = make([]bool, m) } for i := 0; i < n; i++ { for j := 0; j < m; j++ { if dfs(grid, visited, target, i, j, n, m, 0) { return true } } } return false } func dfs(grid [][]byte, visited [][]bool, target string, i, j, n, m, start int) bool { if grid[i][j] != target[start] { return false } if start == len(target)-1 { return true } visited[i][j] = true for idx := 0; idx < 4; idx++ { x := i + dirs[idx] y := j + dirs[idx+1] if x < 0 || x >= n || y < 0 || y >= m { continue } if visited[x][y] { continue } if dfs(grid, visited, target, x, y, n, m, start+1) { return true } } visited[i][j] = false return false } ``` # 全排列II 这道题相比于全排列，多了一个条件就是要去重，所以用过的相同元素构造出来的顺序不能反过来再次使用，也就是如果 nums[i-1] == nums[i] 且 !visited[i-1]，就不能走这条路构造，避免原本先用 i-1 再用 i 又来一遍先用 i 再用 i-1所造成的重复。 ```go func permuteUnique(nums []int) [][]int { sort.Ints(nums) n := len(nums) res := [][]int{} visited := make([]bool, n) dfs(nums, []int{}, &res, visited, len(nums)) return res } func dfs(nums []int, cur []int, res *[][]int, visited []bool, n int) { if len(cur) == n { tmp := make([]int, n) copy(tmp, cur) *res = append(*res, tmp) return } for i := 0; i < n; i++ { if visited[i] { continue } if i > 0 && nums[i] == nums[i-1] && !visited[i-1] { // 前一轮已经用过i-1和i，i-1和i相同，不能先用i再用i-1，否则重复 continue } visited[i] = true dfs(nums, append(cur, nums[i]), res, visited, n) visited[i] = false } } ``` # 括号生成 这道题就是限制需要有效括号，其实相当于要两个变量，分别统计左括号和右括号，左括号在没填满的情况下可以一直填，但是右括号必须要在有左括号的情况下填。 ```go func generateParenthesis(n int) []string { res := []string{} var dfs func(int, int, []byte) dfs = func(left, right int, cur []byte) { if left == 0 && right == 0 { res = append(res, string(cur)) } if left > 0 { dfs(left-1, right, append(cur, '(')) } if right > left { dfs(left, right-1, append(cur, ')')) } } dfs(n, n, []byte{}) return res } ``` Last modification：July 20, 2025 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用，请随意赞赏
