• 39组合总数

  • 代码随想录 (programmercarl.com)

  • 第一印象

  • 本题的元素能够重复，那么回来条件便是是大于等于目标值。依旧是运用path和result存储值。

  • 讲解观后感

  • sum值能够不作为参数传入递归函数中，直接用target -。但是保有sum值能够便利剪枝。
  • 剪枝操作能够先经过排序使数组单调递加。再运用当时sum与当时值的和来提早停止for循环.

  • 解题代码

  •     func combinationSum(candidates []int, target int) [][]int {
        ans := make([][]int, 0)
        if len(candidates)==0 {
            return ans
        }
        path := []int{}
        sum := 0
        var dfs func(candidates []int, idx int, sum int, target int)
        dfs = func(candidates []int, idx int, sum int, target int) {
            if sum > target {
                return
            }
            if sum == target {
                temp := make([]int, len(path))
                copy(temp, path)
                ans = append(ans, temp)
                return
            }
            for i:=idx;i<len(candidates);i++ {
                sum += candidates[i]
                path = append(path, candidates[i])
                dfs(candidates, i, sum, target)
                path = path[:len(path)-1]
                sum -= candidates[i]
            }
        }
        dfs(candidates, 0, sum, target)
        return ans
    }
  • 剪枝：
  •     func combinationSum(candidates []int, target int) [][]int {
        ans := make([][]int, 0)
        if len(candidates)==0 {
            return ans
        }
        path := []int{}
        sum := 0
        sort.Ints(candidates) //排序操作
        var dfs func(candidates []int, idx int, sum int, target int)
        dfs = func(candidates []int, idx int, sum int, target int) {
            if sum == target {
                temp := make([]int, len(path))
                copy(temp, path)
                ans = append(ans, temp)
                return
            }
            for i:=idx;i<len(candidates)&&sum+candidates[i]<=target;i++ { //剪枝操作
                sum += candidates[i]
                path = append(path, candidates[i])
                dfs(candidates, i, sum, target)
                path = path[:len(path)-1]
                sum -= candidates[i]
            }
        }
        dfs(candidates, 0, sum, target)
        return ans
    }

  • 40组合总数II

  • 代码随想录 (programmercarl.com)

  • 第一印象

  • 本题每个数字只能运用一次，那么递归传参就得+1

  • 讲解观后感

  • 这题的去重操作非常巧妙。关于树形结构中树层与树枝的评论非常形象。
    代码随想录day23|39组合总数40组合总数II131分割回文串|01笔记

  • 解题代码

  • 运用used数组
  •     func combinationSum2(candidates []int, target int) [][]int {
        ans := make([][]int, 0)
        if len(candidates)==0 {
            return ans
        }
        path := []int{}
        sum := 0
        sort.Ints(candidates) //排序操作
        used := make([]bool, len(candidates))
        var dfs func(candidates []int, target int,idx int, sum int)
        dfs = func(candidates []int, target int,idx int, sum int) {
            // if sum > target {
            //     return
            // }
            if sum == target {
                temp := make([]int, len(path))
                copy(temp, path)
                ans = append(ans, temp)
                return
            }
            for i:=idx;i<len(candidates)&&sum+candidates[i]<=target;i++ {
                // used[i - 1] == true，阐明同一树枝candidates[i - 1]运用过
                // used[i - 1] == false，阐明同一树层candidates[i - 1]运用过
                if i > 0 && candidates[i] == candidates[i-1]  && used[i-1] == false { 
                    continue
                }
                sum += candidates[i]
                path = append(path, candidates[i])
                used[i] = true
                dfs(candidates, target, i+1, sum)
                used[i] = false
                path = path[:len(path)-1]
                sum -= candidates[i]
            }
        }
        dfs(candidates, target, 0, sum)
        return ans
    }
  • 不运用used数组
  •     func combinationSum2(candidates []int, target int) [][]int {
        ans := make([][]int, 0)
        if len(candidates)==0 {
            return ans
        }
        path := []int{}
        sum := 0
        sort.Ints(candidates) //排序操作
        var dfs func(candidates []int, target int,idx int, sum int)
        dfs = func(candidates []int, target int,idx int, sum int) {
            if sum == target {
                temp := make([]int, len(path))
                copy(temp, path)
                ans = append(ans, temp)
                return
            }
            for i:=idx;i<len(candidates)&&sum+candidates[i]<=target;i++ {
                // i != start 约束了这不对深度遍历抵达的此值去重
                if i != idx && candidates[i] == candidates[i-1] { // 去重
                    continue
                }
                sum += candidates[i]
                path = append(path, candidates[i])
                dfs(candidates, target, i+1, sum)
                path = path[:len(path)-1]
                sum -= candidates[i]
            }
        }
        dfs(candidates, target, 0, sum)
        return ans
    }
  • 不运用sum传参
  •     var (
        res [][]int
        path  []int
    )
    func combinationSum2(candidates []int, target int) [][]int {
        res, path = make([][]int, 0), make([]int, 0, len(candidates))
        sort.Ints(candidates)   // 排序，为剪枝做准备
        dfs(candidates, 0, target)
        return res
    }
    func dfs(candidates []int, start int, target int) {
        if target == 0 {   // target 不断减小，假如为0阐明达到了目标值
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > target {  // 剪枝，提早回来
                break
            }
            // i != start 约束了这不对深度遍历抵达的此值去重
            if i != start && candidates[i] == candidates[i-1] { // 去重
                continue
            }
            path = append(path, candidates[i])
            dfs(candidates, i+1, target - candidates[i])
            path = path[:len(path) - 1]
        }

  • 131切开回文串

  • 代码随想录 (programmercarl.com)

  • 讲解观后感

  • 本题也是经典的运用回溯算法的标题。而关于回溯的用法中，首要遇到的难点便是切开终究应该怎么表示。只要把index和i构成的区间是切开后的区间了解明白，就能解决了。
  • 卡尔也帮我们列出了这道题的几个难点，协助我们了解。
  •     切开问题能够抽象为组合问题
    怎么模拟那些切开线
    切开问题中递归怎么停止
    在递归循环中怎么截取子串
    怎么判断回文

  • 解题代码

  •     var (
        path []string  // 放已经回文的子串
        res  [][]string
    )
    func partition(s string) [][]string {
        path, res = make([]string, 0), make([][]string, 0)
        dfs(s, 0)
        return res
    }
    func dfs(s string, start int) {
        if start == len(s) { // 假如开始位置等于s的巨细，阐明已经找到了一组切开计划了
            tmp := make([]string, len(path))
            copy(tmp, path)
            res = append(res, tmp)
            return 
        }
        for i := start; i < len(s); i++ {
            str := s[start : i+1]
            if isPalindrome(str) {   // 是回文子串
                path = append(path, str)
                dfs(s, i+1)         // 寻找i+1为开始位置的子串
                path = path[:len(path)-1]  // 回溯过程，弹出本次已经填在的子串
            }
        }
    }
    func isPalindrome(s string) bool {
        for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
            if s[i] != s[j] {
                return false
            }
        }
        return true
    }