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

Question

我正在做一个DP课程来复习（这很好，帮了我很多），其中一个问题是给定一个目标和一个数字列表，是否有一条通往目标的路径/最佳（最短）路径是什么

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

下面是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

仅供参考，上面发布的解决方案给出了不正确的答案，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

Answer 2

当前算法的问题是递归函数只能返回一个可能的解；例如，当它到达12、[2 2]时，有多个解决方案（包括[2 2 2 10 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
}

游乐场