溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
回溯算法實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就 “回溯” 返回，嘗試別的路徑。回溯法是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為 “回溯點”。許多復雜的，規模較大的問題都可以使用回溯法，有“通用解題方法”的美稱。
回溯算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
鏈接：https://leetcode-cn.com/tag/backtracking/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。本文主要總結一下回溯算法的一些題目。語言主要是Golang。
第一種是比較常規的回溯解法。
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
}常規解法。當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]
}
}常規解法，要先排序一下。每次先嘗試減去當前元素，要是減去后還大于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
}
}
}和第一個很像，但是每個數字只能用一次且解空間不能包含重復解。
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
}
}
}
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
}
}
}
方法一是常規的回溯。
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
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
