IT博客汇 | 『代码随想录』回溯（Backtracking）

『代码随想录』回溯（Backtracking）

NX の博客发表于 2023-11-17 03:41:16

DAY 24

77.组合

很经典的回溯算法

func combine(n int, k int) [][]int {
    ans := [][]int{}
    curr := []int{}
    var dfs func(s int)
    dfs = func(s int) {
        if len(curr) == k {
            ans = append(ans, append([]int{}, curr...))
            return
        }
        for i := s; i <= n; i++ {
            curr = append(curr, i)
            dfs(i + 1)
            curr = curr[:len(curr)-1]
        }
    }
    dfs(1)
    return ans
}

做了一点剪枝

  package main

  func combine(n int, k int) [][]int {
      ans := [][]int{}
      curr := []int{}
      var dfs func(s int)
      dfs = func(s int) {
          if len(curr) == k {
              ans = append(ans, append([]int{}, curr...))
              return
          }
-       for i := s; i <= n; i++ {
+       for i := s; i <= n-(k-len(curr))+1; i++ {
              curr = append(curr, i)
              dfs(i + 1)
              curr = curr[:len(curr)-1]
          }
      }
      dfs(1)
      return ans
  }

DAY 25

216.组合总和 III

很顺理成章的递归

func combinationSum3(k int, n int) [][]int {
    ans := [][]int{}
    curr := []int{}
    var dfs func(s, k, n int)
    dfs = func(s, k, n int) {
        if k == 0 || n < 0 {
            if n == 0 {
                ans = append(ans, append([]int{}, curr...))
            }
            return
        }
        for i := s; i <= 9; i++ {
            curr = append(curr, i)
            dfs(i+1, k-1, n-i)
            curr = curr[:len(curr)-1]
        }
    }
    dfs(1, k, n)
    return ans
}

17.电话号码的字母组合

之前刷的时候写的是 BFS 的，这次特意写了个递归的

var m = [][]string{
    {}, {}, {"a", "b", "c"}, {"d", "e", "f"}, {"g", "h", "i"}, {"j", "k", "l"}, {"m", "n", "o"}, {"p", "q", "r", "s"}, {"t", "u", "v"}, {"w", "x", "y", "z"},
}

func letterCombinations(digits string) []string {
    n := len(digits)
    if n == 0 {
        return []string{}
    }else if n == 1 {
        return m[int(digits[0]-'0')]
    }
    ans := []string{}
    pre := letterCombinations(digits[1:])
    for _, i := range pre {
        for _, j := range m[int(digits[0]-'0')] {
            ans = append(ans, j+i)
        }
    }
    return ans
}

DAY 26

周日休息，去逛了 Gopher China（

DAY 27

39.组合总和

func combinationSum(candidates []int, target int) [][]int {
    n := len(candidates)
    ans := [][]int{}
    curr := []int{}
    var dfs func(idx, need int)
    dfs = func(idx, need int) {
        if need < 0 {
            return
        } else if need == 0 {
            ans = append(ans, append([]int{}, curr...))
        } 
        for i := idx; i < n; i++ {
            curr = append(curr, candidates[i])
            dfs(i, need-candidates[i])
            curr = curr[:len(curr)-1]
        }
    }
    dfs(0, target)
    return ans
}

40.组合总和 II

这道题麻烦的地方在于去重，真得看代码随想录

如果与前一个元素相同且前一个元素没有使用过，则跳过

func combinationSum2(candidates []int, target int) [][]int {
    n := len(candidates)
    sort.Ints(candidates)
    ans := [][]int{}
    curr := []int{}
    used := make([]bool, n)
    var dfs func(idx, need int)
    dfs = func(idx, need int) {
        if need < 0 {
            return
        } else if need == 0 {
            ans = append(ans, append([]int{}, curr...))
        }

        for i := idx; i < n; i++ {
            if i > 0 && candidates[i] == candidates[i-1] && !used[i-1] {
                continue // 这里是关键
            }
            curr = append(curr, candidates[i])
            used[i] = true
            dfs(i+1, need-candidates[i])
            curr = curr[:len(curr)-1]
            used[i] = false
        }
    }
    dfs(0, target)
    return ans
}

131.分割回文串

这道题貌似还可以用 dp

func partition(s string) [][]string {
    ans := [][]string{}
    curr := []string{}
    var dfs func(s string)
    dfs = func(s string) {
        n := len(s)
        if n == 0 {
            ans = append(ans, append([]string{}, curr...))
            return
        }
        for i := 1; i <= n; i++ {
            if isPalindrome(s[:i]) {
                curr = append(curr, s[:i])
                dfs(s[i:])
                curr = curr[:len(curr)-1]
            }
        }
    }
    dfs(s)
    return ans
}

func isPalindrome(s string) bool {
    if len(s) == 1 {
        return true
    } else if len(s) == 2 {
        if s[0] == s[1] {
            return true
        } else {
            return false
        }
    } else {
        return s[0] == s[len(s)-1] && isPalindrome(s[1:len(s)-1])
    }
}

DAY 28

93.复原 IP 地址

细节有点多，需要注意

func restoreIpAddresses(s string) []string {
    ans := []string{}
    curr := []string{}
    var dfs func(s string)
    dfs = func(s string) {
        if len(curr) == 4 || s == "" {
            if len(curr) == 4 && s == "" {
                ans = append(ans, combine(curr))
            }
            return
        }

        if s[0] == '0' {
            curr = append(curr, string(s[0]))
            dfs(s[1:])
            curr = curr[:len(curr)-1]
            return
        }

        for i := 1; i <= len(s); i++ {
            if atoi(s[:i]) > 255 {
                break
            }
            curr = append(curr, s[:i])
            dfs(s[i:])
            curr = curr[:len(curr)-1]
        }
    }
    dfs(s)
    return ans
}

func atoi(s string) int {
    ans := 0
    for _, ch := range s {
        ans = ans*10 + int(ch) - '0'
    }
    return ans
}

func combine(s []string) string {
    ans := ""
    for _, item := range s {
        ans = ans + item + "."
    }
    return ans[:len(ans)-1]
}

78.子集

一气呵成，非常舒服

func subsets(nums []int) [][]int {
    ans := [][]int{}
    curr := []int{}
    targetLen := 0
    var dfs func(nums []int)
    dfs = func(nums []int) {
        if len(curr) == targetLen {
            ans = append(ans, append([]int{}, curr...))
            return
        }
        for i := 0; i < len(nums); i++ {
            curr = append(curr, nums[i])
            dfs(nums[i+1:])
            curr = curr[:len(curr)-1]
        }
    }
    for targetLen = 0; targetLen <= len(nums); targetLen++ {
        dfs(nums)
    }
    return ans
}

90.子集 II

为了去重，有一点小小的 diff

func subsetsWithDup(nums []int) [][]int {
+     sort.Ints(nums)
      ans := [][]int{}
      curr := []int{}
      targetLen := 0
      var dfs func(nums []int)
      dfs = func(nums []int) {
          if len(curr) == targetLen {
              ans = append(ans, append([]int{}, curr...))
              return
          }
          for i := 0; i < len(nums); i++ {
+             if i > 0 && nums[i] == nums[i-1] {
+                 continue
+             }
              curr = append(curr, nums[i])
              dfs(nums[i+1:])
              curr = curr[:len(curr)-1]
          }
      }
      for targetLen = 0; targetLen <= len(nums); targetLen++ {
          dfs(nums)
      }
      return ans
  }

DAY 29

491.递增子序列

这道题去重是关键，我一开始去重写错了，后来喂给 GPT 他把我教会了

func findSubsequences(nums []int) [][]int {
    var ans [][]int
    var curr []int
    var dfs func(nums []int)
    dfs = func(nums []int) {
        if len(curr) >= 2 {
            ans = append(ans, append([]int{}, curr...))
        }
        used := map[int]bool{} // 这里是关键
        for i := 0; i < len(nums); i++ {
            if used[nums[i]] {
                continue
            }
            if len(curr) > 0 && curr[len(curr)-1] > nums[i] {
                continue
            }
            used[nums[i]] = true
            curr = append(curr, nums[i])
            dfs(nums[i+1:])
            curr = curr[:len(curr)-1]
        }
    }
    dfs(nums)
    return ans
}

这个 map 的作用是在当前层不重复，比如 [4,6,7,7] ，你不去重就会搜到两个 [4,6,7]

而使用 map，当你搜到 4->6 的时候，搜到第一个 7，把 7 标记一下，下一个 7 就能跳过了

46.全排列

向下递归的时候在可选集合中剔除当前元素

func permute(nums []int) [][]int {
    ans := [][]int{}
    curr := []int{}
    var dfs func(nums []int)
    dfs = func(nums []int) {
        if len(nums) == 0 {
            ans = append(ans, append([]int{}, curr...))
            return
        }
        for i := 0; i < len(nums); i++ {
            curr = append(curr, nums[i])
            tmp := append([]int{}, nums[:i]...)
            tmp = append(tmp, nums[i+1:]...)
            dfs(tmp)
            curr = curr[:len(curr)-1]
        }
    }
    dfs(nums)
    return ans
}

或者你可以使用一个 []bool 标记已经剔除的元素

func permute(nums []int) [][]int {
    n := len(nums)
    ans := [][]int{}
    curr := []int{}
    used := make([]bool, n)
    var dfs func(depth int)
    dfs = func(depth int) {
        if depth == n {
            ans = append(ans, append([]int{}, curr...))
            return
        }
        for i := 0; i < n; i++ {
            if used[i] {
                continue
            }
            curr = append(curr, nums[i])
            used[i] = true
            dfs(depth + 1)
            used[i] = false
            curr = curr[:len(curr)-1]
        }
    }
    dfs(0)
    return ans
}

47. 全排列 II

与 [40.组合总和 II](#40.组合总和 II) 的去重思路相同，首先排序

然后如果用过，或者与前一个相同并且前一个没用过，就跳过

（当我们有连续的重复元素时，为了避免生成相同的排列，我们只在这些重复元素的第一次出现时考虑它们）

- func permute(nums []int) [][]int {
+ func permuteUnique(nums []int) [][]int {
    n := len(nums)
+   sort.Ints(nums)
    ans := [][]int{}
    curr := []int{}
    used := make([]bool, n)
    var dfs func(depth int)
    dfs = func(depth int) {
      if depth == n {
        ans = append(ans, append([]int{}, curr...))
        return
      }
      for i := 0; i < n; i++ {
-       if used[i] {
+       if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
          continue
        }
        curr = append(curr, nums[i])
        used[i] = true
        dfs(depth + 1)
        used[i] = false
        curr = curr[:len(curr)-1]
      }
    }
    dfs(0)
    return ans
  }

DAY 30

332. 重新安排行程

~~泻药，欧拉回路，还是算了~~

51. N 皇后

经典 N 皇后，看了一眼，有点忙不想做

37. 解数独

一样