跳至主要內容

1.(或许有时递归函数是万能的)回溯算法-在语法层面的写法是递归

whoway2026/2/1大约 10 分钟

1.(或许有时递归函数是万能的)回溯算法-在语法层面的写法是递归

我的习惯是，进行回溯的那个递归函数，我写为bt函数（backtrack）回溯

回溯算法的解决方案：
1、一定要记得使用递归函数！【强调，递归递归递归！】
2、递归函数的定义你要先定义抽象，最后再去确认相关参数要哪些！

77. 组合

方法1使用k层for循环暴力
// 核心问题就是：从逻辑上暴力确实可行！但是语法上根本写不出来
// 当 k 是变量时，我们无法在编译时确定需要多少层循环，所以不能硬编码多层嵌套的 for 循环。
// 这正好体现了递归/回溯算法的必要性——它可以动态地处理可变深度的嵌套

  // k为1
for i:=0 ; i < length ; i++ {
	// k为2
  for j:=i+1 ; j < length ; j++ {
	//  k为3
    for k:=j+1 ; k < length ; k++ {
		// k为4
      for l:=k+1 ; l < length ; l++ {
		//  省略 // 甚至还要继续加
        for m:=l+1 ; m < length ; m++ {
          for n:=m+1 ; n < length ; n++ {
        }
      }
    }
  }
}

131. 分割回文串

方法1使用回溯算法
func partition(s string) [][]string {
    globalRes := [][]string{}
    curSplitList := []string{}
	// ✅
    bt(&globalRes, &curSplitList, s, 0, 1)
    return globalRes
}

// 指定在哪个划分点去划分, 划分点的意思是小于这个点的为1块，大于等于这个点的为1块
// 划分[lastSplitIndex,trySplitIndex)
// 上一次划分的点，本次尝试划分也可能不划分的点
// ✅
func bt(globalRes *[][]string, curSplitList *[]string, s string , lastSplitIndex int, trySplitIndex int) {
    // 递归函数的边界：划分点 == s 的长度, 是最后的可能划分点了
    if trySplitIndex == len(s) {
		// ✅
        *curSplitList = append(*curSplitList,s[lastSplitIndex:trySplitIndex])
        // 这种情况下，我们根本就不存在这个划分点的后面1部分
        if helpFuncJudge(curSplitList) {
            tmp := make([]string, len(*curSplitList))
			// ✅
            copy(tmp,*curSplitList)
            *globalRes = append(*globalRes, tmp)
        }
        return 
    }

    btIndex := len(*curSplitList) // 先保留，现在这个还没选择前的slice长度
    // 如果在当前划分
    *curSplitList = append(*curSplitList,s[lastSplitIndex:trySplitIndex])
    bt(globalRes,curSplitList, s, trySplitIndex, trySplitIndex+1)

    // 如果在当前不划分
    *curSplitList = (*curSplitList)[:btIndex]
    bt(globalRes,curSplitList, s, lastSplitIndex, trySplitIndex+1)

}

// 辅助函数
func helpFuncJudge(tmp *[]string) bool {
    if len(*tmp) == 0 {
        return false // 不能加入结果
    }
    for _, s := range *tmp {
        length := len(s)
        left := 0
        right := length-1
        for left < right{
            if s[left] != s[right] {
                return false 
            }
            left++
            right--
        }
    }
    return true
}

17. 电话号码的字母组合【hot100】

最简单的直接暴力遇到的问题还是：如何写出for循环的层数，发现不能，那就借助递归来解决这种层次结构极其相似的循环！

  • 细节1：使用回溯算法，如果用了临时变量了，那就不用撤销了
  • 细节2：string(digits[index]) 字符串索引后是byte，需要强制转换为string才能被那个key是string的map使用
方法1使用回溯算法，如果用了临时变量了，那就不用撤销了
func letterCombinations(digits string) []string {
    globalMap := map[string][]string{
        "2": []string {
            "a", "b", "c",
        },
        "3": []string {
            "d", "e", "f",
        },
        "4": []string {
            "g", "h", "i",
        },
        "5": []string {
            "j", "k", "l",
        },
        "6": []string {
            "m", "n", "o",
        },
        "7": []string {
            "p", "q", "r", "s",
        },
        "8": []string {
            "t", "u", "v",
        },
        "9": []string {
            "w", "x", "y", "z",
        },
    }

    globalRes := []string{}

    bt(globalMap,&globalRes,"", digits, 0)
    return globalRes
}


// 尝试选择index位置的元素
func bt(globalMap map[string][]string, globalRes *[]string, curStr string, digits string, index int) {
    if index > len(digits) - 1 {
        return 
    }
    // 最后1个元素了
    if index == len(digits) - 1 {
        for _ , v := range globalMap[string(digits[index])] {
            // 使用临时变量，就不用撤销不撤销了
            tmp := curStr + v
            *globalRes = append(*globalRes, tmp)
        }
        return 
    }

    // 如果不是最后的元素，那么按照顺序遍历即可
    for _ , v := range globalMap[string(digits[index])] {
        // 使用临时变量，就不用撤销不撤销了
        tmp := curStr + v
        bt(globalMap, globalRes, tmp, digits, index+1)
    }
}

301. 删除无效的括号困难题也能层次递进的进行剪枝，最终总算通过了【hot100】

方法1使用回溯算法，虽然超时，但是逻辑对(125 / 129)
func removeInvalidParentheses(s string) []string {
    globalRes := []string{}
    length := len(s)
    delIndex := make([]int, length)

    // 1.遍历可能的删除个数，内部使用回溯
    for i := 0 ; i < length ; i++ {
        bt(&globalRes, s, delIndex, i, 0, 0)
        // 如果删除i个括号就能行了，那不用删了
        if len(globalRes) > 0 {
            break
        }
    }
    // 2.最特殊的就是全删
    if len(globalRes) == 0 {
        globalRes = append(globalRes, "")
    }
    // 3.将globalRes去重
    mp := map[string]bool{}
    res := []string{}
    for _, v := range globalRes {
        if !mp[v] {
            res = append(res, v)
        }
        mp[v] = true
    }
    return res
}


// 目标是删除几个括号
// delIndex不使用指针，因为我只需要这种临时变量
func bt(globalRes *[]string, s string, delIndex []int, targetDelNums int, curHadDelNums int, curIndex int) {
    if curHadDelNums == targetDelNums {
        tmp := ""
        for k, v := range delIndex {
            if v == 0 {
                tmp += string(s[k])
            }
        }

        if isValid(tmp) {
            *globalRes = append(*globalRes, tmp)
        }
        return 
    }
    if curIndex >= len(s) {
        return 
    }

    curStr := string(s[curIndex])
    if curStr != "(" && curStr != ")" {
        bt(globalRes, s, delIndex, targetDelNums, curHadDelNums, curIndex+1)
        return 
    }

    // 选择这个下标删除
    delIndex[curIndex] = 1
    bt(globalRes, s, delIndex, targetDelNums, curHadDelNums+1, curIndex+1)

    // 这个下标我不选择删除
    delIndex[curIndex] = 0 
    bt(globalRes, s, delIndex, targetDelNums, curHadDelNums, curIndex+1)
}

// 判断某字符串是否合法
func isValid(tmp string) bool {
    Left := 0
    Right := 0
    for _, v := range tmp {
        if string(v) == "(" {
            if Right != 0 {
                return false
            }
            Left++
        }else if string(v) == ")" {
            if Left > 0 {
                Left--
            }else{
                return false
            }
        }
    }

    return Left == 0 && Right == 0
}

至此，感觉这种传统优化不够看了，还得想一些超级无敌的剪枝方式

  • 再深入思考一下的剪枝：先算最少需要删除多少个括号，这样将for暴力直接缩减？看看行不行
    原理
  • rremove：前面没有 '(' 能匹配的 ')'
  • lremove：最终剩下、没人要的 '('
    这两类括号 永远不可能通过重新排列或补救配对，所以只能删除，因此最少删除数 = lremove + rremove

下面的代码做了3次剪枝，总算通过了！

func removeInvalidParentheses(s string) []string {
    globalRes := []string{}
    length := len(s)
    delIndex := make([]int, length)

    // 1.遍历可能的删除个数，内部使用回溯
    // for i := 0 ; i < length ; i++ {
    //     bt(&globalRes, s, delIndex, i, 0, 0)
    //     // 如果删除i个括号就能行了，那不用删了
    //     if len(globalRes) > 0 {
    //         break
    //     }
    // }

    // 优化，更加深入剪枝：calcMinDel
    nums := calcMinDel(s)
    for i := nums ; i < length ; i++ {
        bt(&globalRes, s, delIndex, i, 0, 0)
        // 如果删除i个括号就能行了，那不用删了
        if len(globalRes) > 0 {
            break
        }
    }

    // 2.最特殊的就是全删
    if len(globalRes) == 0 {
        globalRes = append(globalRes, "")
    }
    // 3.将globalRes去重
    mp := map[string]bool{}
    res := []string{}
    for _, v := range globalRes {
        if !mp[v] {
            res = append(res, v)
        }
        mp[v] = true
    }
    return res
}


// 目标是删除几个括号
// delIndex不使用指针，因为我只需要这种临时变量
func bt(globalRes *[]string, s string, delIndex []int, targetDelNums int, curHadDelNums int, curIndex int) {
    
    if curHadDelNums == targetDelNums {
        tmp := ""
        for k, v := range delIndex {
            if v == 0 {
                tmp += string(s[k])
            }
        }
        if isValid(tmp) {
            *globalRes = append(*globalRes, tmp)
        }
        return 
    }

    if curIndex >= len(s) {
        return 
    }


    // 优化一下：做个剪枝, 如果剩下的需要删除的个数大于剩下的长度，那就直接剪枝
    if (targetDelNums - curHadDelNums) > len(s) - curIndex {
        return 
    }
    // 优化一下，做个剪枝，如果未来都不可能了，直接return吧
    tmp := ""
    for index, v := range delIndex {
        if index == curIndex {
            break
        }
        if v == 0 {
            tmp += string(s[index])
        }
    }
    if !calcFutureMaybeOK(tmp) {
        return 
    }

    curStr := string(s[curIndex])
    if curStr != "(" && curStr != ")" {
        bt(globalRes, s, delIndex, targetDelNums, curHadDelNums, curIndex+1)
        return 
    }

    // 选择这个下标删除
    delIndex[curIndex] = 1
    bt(globalRes, s, delIndex, targetDelNums, curHadDelNums+1, curIndex+1)

    // 这个下标我不选择删除
    delIndex[curIndex] = 0 
    bt(globalRes, s, delIndex, targetDelNums, curHadDelNums, curIndex+1)
}

// 判断某字符串是否合法
func isValid(tmp string) bool {
    Left := 0
    Right := 0
    for _, v := range tmp {
        if string(v) == "(" {
            if Right != 0 {
                return false
            }
            Left++
        }else if string(v) == ")" {
            if Left > 0 {
                Left--
            }else{
                return false
            }
        }
    }

    return Left == 0 && Right == 0
}

// 如果现在的字符串
// 形成了多余的)结构，未来没必要了
func calcFutureMaybeOK(tmp string) bool {
    Left := 0
    for _, v := range tmp {
        if string(v) == "(" {
            Left++
        }else if string(v) == ")" {
            if Left > 0 {
                Left--
            }else {
                // 形成了多余的)结构，，未来没必要了
                return false
            }
        }
    }
    // 未来还有改善的机会
    return true
}

// 最少删除数 = lremove + rremove
//lremove：多余的 (
//rremove：多余的 )
func calcMinDel(s string) int {
    lremove := 0
    rremove := 0
    for _, c := range s {
        if c == '(' {
            lremove++
        } else if c == ')' {
            if lremove > 0 {
                lremove--
            } else {
                rremove++
            }
        }
    }
    return lremove + rremove
}