动态规划问题 - 扩展以找到求和的所有可能路径

Question

我正在做 DP course 复习（这很棒，对我帮助很大），其中一个问题是 given a target sum and a list of numbers, is there a path to the target / what is the best (shortest) path?

我已经解决了 pathExists 和 bestPath 问题，但一直在思考一个他们没有要求解决的问题 - 你能列出解决方案的所有路径吗：

下面的 golang 代码最好

golang

func BestSum(ts int, nums []int) []int {
    var best []int
    return bs(ts, nums, best)
}

func bs(ts int, nums, best []int) []int {
    if ts == 0 {
        return []int{}
    } else if ts < 0 {
        return nil
    }

    for _, n := range nums {
        rc := bs(ts-n, nums, best)
        if rc != nil {
            path := append(rc, n)
            if best == nil || len(best) > len(path){
                best = path
            }           
        }
    }

    return best
}

// 例如： BestSum(7, [5,3,4,7]) // 答案：[7]

既然我们在这里涵盖了所有路径，我想看看我是否可以 return 所有路径，但我陷入了一段逻辑：

func AllSum(ts int, nums []int) [][]int {
    all := [][]int{}

    var as func(int, []int) []int 
    as = func(s int, nums []int) []int {
        if s == 0 {
            return []int{}
        } else if s < 0 {
            return nil
        }
    
        var path []int
        for _, n := range nums {
            rc := as(s-n, nums)
            if rc != nil {
                path = append(rc, n)
// this section iterates over path so far each time (slow) and sums to see if it can append yet
                var sum int
                for _, c := range path {
                    sum+=c
                }
                if sum == ts {
                    all = append(all, path)
                }
            }
        }
    
        return path
    }

    _ = as(ts, nums)
    return all
}

上面的代码通过了 7, [5,4,3,7] 但没有通过 20, [2,10] 缺少 [2,2,2,2,2,2,2,2,2,2]

是否有一种众所周知的模式可以从递归生成路径的函数中收集所有路径？

Answer 1

您当前算法的问题是递归函数只能return一种可能的解决方案；例如，当它到达 12, [2 2 2 2] 时，有不止一种解决方案（包括 [2 2 2 2 10 2] 和 [2,2,2,2,2,2,2,2,2,2]），但你只会 return 一个（你检查所有路径，但许多结果被扔掉了）。

一个常见的解决方案是将路径传递给递归函数；例如：

package main

import (
    "fmt"
)

func main() {
    fmt.Println(AllSum(20, []int{2, 10}))
    fmt.Println(AllSum(7, []int{5,4,3,7}))
}

func AllSum(ts int, nums []int) [][]int {
    return allSum(ts, nums, nil)
}

func allSum(s int, nums []int, path []int) [][]int {
    if s < 0 {
        return nil // No solution here
    }
    if s == 0 { // solution found
        return [][]int{path}
    }
    
    // Copy the path to avoid editing other solutions
    p := make([]int, len(path))
    copy(p, path)
    
    var solutions [][]int
    for _, n := range nums {
        rc := allSum(s-n, nums, append(p, n))
        if rc != nil {
            solutions = append(solutions, rc...)
        }
    }
    return solutions
}

playground

Answer 2

仅供参考，上面发布的解决方案给出了错误的答案，而 DP 课程实际上继续解释了一个类似问题的解决方案，让我找到了这个问题的解决方案：

func AllSum(ts int, nums []int) [][]int {
    return as(ts, nums)
} 

func as(s int, nums []int) [][]int {
    if s == 0 {
        return [][]int{{}}
    }
    
    var all [][]int
    for _, n := range nums {
        if s-n < 0{
            continue
        }

        paths := as(s-n, nums)
        for i, _ := range paths {
            paths[i] = append(paths[i], n)
            all = append(all, paths[i])
        }
    }

    return all
}

链接到固定代码：https://play.golang.org/p/cpEKgV2e1kM

动态规划问题 - 扩展以找到求和的所有可能路径

Dynamic Programming problem - extending to find all possible paths to sum

dynamic-programming

go