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

Question

我正在做一个DP课程来复习(它很棒，帮助了我很多)，其中一个问题是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])//ans: [7]

因为我们在这里涵盖了所有的路径，我想看看我是否可以返回所有的路径，但是在逻辑上卡住了:

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

当前算法的问题是递归函数只能返回一个可能的解;例如，当它到达12, [2 2 2 2]时，有多个解决方案(包括[2 2 2 2 10 2]和[2,2,2,2,2,2,2,2,2,2])，但您将只返回一个(您检查所有路径，但许多结果被丢弃)。

一个常见的解决方案是将路径传递给递归函数;例句:

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
}

游乐场

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