回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就 “回溯” 返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为 “回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
链接：https://leetcode-cn.com/tag/backtracking/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
本文主要总结一下回溯算法的一些题目。语言主要是Golang。
[78.子集，不含重复元素][78.]
第一种是比较常规的回溯解法。
func subsets(nums []int) [][]int {
result := make([][]int, 0)
subsetsBT(&result, nums, []int{}, 0)
return result
}
func subsetsBT(result *[][]int, nums []int, temp []int, start int) {
//此处深拷贝temp，避免回溯的时候temp被修改后会影响之前保存的结果
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
for i := start; i < len(nums); i++ {
temp = append(temp, nums[i])
subsetsBT(result, nums, temp, i+1)//不包含重复值
temp = temp[:len(temp)-1]
}
}
第二章方法就比较牛逼了，具体解释参考此处。用二进制位的0，1表示是否选中当前位置的数。
func subsets(nums []int) [][]int {
result := make([][]int, 0)
n := 1 << uint(len(nums))
for i := 0; i < n; i++ {
temp := make([]int, 0)
for j := 0; j < len(nums); j++ {
if uint(i)>>uint(j)&1 == 1 {
temp = append(temp, nums[j])
}
}
result = append(result, temp)
}
return result
}
[77.组合][77.]
常规解法。当temp里的元素个数等于给定的K时，找到一个满足条件的解。
func combine(n int, k int) [][]int {
var result = make([][]int, 0)
combineBT(n, k, 1, []int{}, &result)
return result
}
func combineBT(n, k, start int, temp []int, result *[][]int) {
if len(temp) == k {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i <= n; i++ {
temp = append(temp, i)
combineBT(n, k, i+1, temp, result)
temp = temp[0 : len(temp)-1]
}
}
[39. 组合总和，不包含重复元素，可多次使用][39.]
常规解法，要先排序一下。每次先尝试减去当前元素，要是减去后还大于0，则表示可以继续往下走。然后因为可以重复使用元素，所以回溯的时候从i开始继续下一次。直到目标值减到0后，找到一个满足条件的解空间。
func combinationSum(candidates []int, target int) [][]int {
var result = make([][]int, 0)
sort.Ints(candidates)
combinationSumBT(&result, candidates, []int{}, target, 0)
return result
}
func combinationSumBT(result *[][]int, candidates []int, temp []int, target int, start int) {
if target == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i < len(candidates); i++ {
if target-candidates[i] >= 0 {
target -= candidates[i]
temp = append(temp, candidates[i])
combinationSumBT(result, candidates, temp, target, i)//可以包含已经用过的值，所以从i开始，
temp = temp[0 : len(temp)-1]//回溯
target += candidates[i]//得把当前用过的值再加回去。
} else {
return
}
}
}
[40. 组合总和2，只能使用一次且解空间不能包含重复][40. _2]
和第一个很像，但是每个数字只能用一次且解空间不能包含重复解。
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
var result = make([][]int, 0)
combinationSumBT2(&result, candidates, []int{}, target, 0)
return result
}
func combinationSumBT2(result *[][]int, candidates []int, temp []int, target int, start int) {
if target == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i < len(candidates); i++ {
if target-candidates[i] >= 0 {
//比如[10,1,2,7,6,1,5], target = 8
//排好序后[1,1,2,5,6,7,10]
//在第一个for循环里，先遍历到第一个1，经过一系列操作，得到解集[1,7]
//然后还是第一个for循环里，又遍历到后面的1，现在是不需要[第二个1,7]这个解集了，所以跳过。
if i != start && candidates[i] == candidates[i-1] { //因为解空间不能有重复
continue
}
target -= candidates[i]
temp = append(temp, candidates[i])
combinationSumBT2(result, candidates, temp, target, i+1)//因为不能重复使用，所以从i+1开始
temp = temp[0 : len(temp)-1]
target += candidates[i]
} else {
return
}
}
}
216. 组合总和3,只有1-9，且每个组合中不能有重复且最后的解空间不能包含重复
func combinationSum3(k int, n int) [][]int {
var result = make([][]int, 0)
combinationSumBT3(&result, []int{}, k, n, 1)
return result
}
func combinationSumBT3(result *[][]int, temp []int, k int, target int, start int) {
//和第一个很像，在target的基础上增加了一个k的限制。
if target == 0 && k == 0 {
c := make([]int, len(temp))
copy(c, temp)
*result = append(*result, c)
return
}
for i := start; i <= 9; i++ {
if target-i >= 0 {
target -= i
k--
temp = append(temp, i)
combinationSumBT3(result, temp, k, target, i+1)//每个组合不能有重复
temp = temp[0 : len(temp)-1]
target += i
k++
} else {
return
}
}
}
[17.电话号码的字母组合][17.]
方法一是常规的回溯。
var wordsMap = map[int]string{2: "abc", 3: "def", 4: "ghi", 5: "jkl", 6: "mno", 7: "pqrs", 8: "tuv", 9: "wxyz"}
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
answer := make([]string, 0)
letterCombinationsBT(&answer, digits, "", 0)
return answer
}
func letterCombinationsBT(answer *[]string, digits string, temp string, index int) {
if len(temp) == len(digits) {
*answer = append(*answer, temp)
return
}
char := digits[index] - '0'
letter := wordsMap[int(char)]
//fmt.Println(int(char), letter)
for i := 0; i < len(letter); i++ {
letterCombinationsBT(answer, digits, temp+string(letter[i]), index+1)
}
return
}
方法二就比较牛逼了，把按的数字对应的字母依次放到队列中，然后和下一个数字的字母挨个拼，拼完再扔到队尾。 比如我按了 “23” 对应 abc 和 def 我先在队列[从左到右表示队首到队尾]初始化一个空字符串。
” “
然后遍历第一个数字 2 ，对应的字母是 abc，然后用队列头部的空字符串 “” 依次和abc做拼接，得到 “a”, “b”, “c”, 然后依次从队尾扔到队列，现在队列是
a b c
遍历完2对应的字母再继续遍历3的。3对应def。取出队首的”a”,依次和后面的def拼接，得到 “ad”, “ae”, “af”,然后扔到队尾，现在队列里是
b c ad ae af
继续重复这个操作即可完成最后的遍历，很方便。
c ad ae af bd be bf
ad ae af bd be bf cd ce cf
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
var words = [8]string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
queue := make([]string, 0)
queue = append(queue, "")
for i := 0; i < len(digits); i++ {
n := digits[i] - '2'
size := len(queue)
for j := 0; j < size; j++ {
st := queue[0]
queue = queue[1:]
for _, ch := range words[n] {
temp := st + string(ch)
queue = append(queue, temp)
}
}
}
return queue
}
[79. 单词搜索,一个格子里的单词不许重复使用][79.]
func exist(board [][]byte, word string) bool {
if len(word) == 0 {
return false
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if existWordsBT(board, word, i, j, 0) {
return true
}
}
}
return false
}
var direction = [][]int{{-1, 0}, {0, -1}, {0, 1}, {1, 0}}
func existWordsBT(board [][]byte, word string, i, j, index int) bool {
//遍历到最后一个单词的时候，要是等于就OK
if index == len(word)-1 {
return word[index] == board[i][j]
}
//fmt.Println(index, string(board[i][j]), visited[i][j])
if board[i][j] == word[index] {
temp := board[i][j]
board[i][j] = '%' //标记当前字母被使用过了
//visited[i][j] = 1
for k := 0; k < 4; k++ { //套路，四个方向
newX := i + direction[k][0]
newY := j + direction[k][1]
//四个新方向在格子内且没被用过就可以继续下去了
if newX >= 0 && newX < len(board) && newY >= 0 && newY < len(board[0]) && board[newX][newY] != '%' {
if existWordsBT(board, word, newX, newY, index+1) {
return true
}
}
}
//visited[i][j] = 0
board[i][j] = temp //回溯到没用过当前单词
}
return false
}
695. 岛屿最大面积
func maxAreaOfIsland(grid [][]int) int {
row, col := len(grid), len(grid[0])
ret := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
if grid[i][j] == 1 {
ret = int(math.Max(float64(dfs(grid, i, j, 0)), float64(ret)))
}
}
}
return ret
}
func dfs(grid [][]int, i int, j int, sum int) int {
row, col := len(grid), len(grid[0])
if i < 0 || j < 0 || i >= row || j >= col || grid[i][j] != 1 {
return 0
}
sum++
grid[i][j] = 9
sum += dfs(grid, i-1, j, 0)
sum += dfs(grid, i+1, j, 0)
sum += dfs(grid, i, j-1, 0)
sum += dfs(grid, i, j+1, 0)
return sum
}
下面这种应该也是可以的。而且从结果来看比第一张方法还快一些。
func maxAreaOfIsland2(grid [][]int) int {
row, col := len(grid), len(grid[0])
ret := 0
for i := 0; i < row; i++ {
for j := 0; j < col; j++ {
ret = myMax(ret, maxAreaBT(grid, i, j, 0))
}
}
return ret
}
func maxAreaBT(grid [][]int, i int, j int, sum int) int {
row, col := len(grid), len(grid[0])
if i < 0 || j < 0 || i >= row || j >= col || grid[i][j] != 1 {
return 0
}
if grid[i][j] == 1 {
grid[i][j] = 9
sum++
fmt.Println(i, j, sum)
for k := 0; k < 4; k++ {
newX := i + direction[k][0]
newY := j + direction[k][1]
if newX >= 0 && newY >= 0 && newX < row && newY < col && grid[newX][newY] == 1 {
fmt.Println(99, newX, newY, sum, grid)
sum = maxAreaBT(grid, newX, newY, sum)
}
}
//grid[i][j] = 1
return sum
} else {
return 0
}
}