获取幂和问题的所有可能组合

Question

我正在尝试找出构成幂和的所有数字组合。下面是我的代码，在找到第一个组合后 returns。

`代码：

def powerSum(targetSum, N):
    def helper(x,n,c):
        if pow(c,n)==x:
            return [c]
        if pow(c,n)>x:
            return None
        l = helper(x,n,c+1)
        r = helper(x-pow(c,n),n,c+1)
        if l!=None or r!=None:
            if l==None:
                return r+[c]
            else:
                return l
    return helper(targetSum,N,1)
print(powerSum(100,2))

谁能帮我 return 所有可能的组合例子：如果输入是 targetSum =100 和 N=2 输出应该是三个可能组合列表的列表 =[[10],[6,8][1,3,4,5,7]] 我的输出只有 [10]

Answer 1

重新考虑 return 类型：

def powerSum(targetSum, N):
    def helper(x, n, c):
        if pow(c, n) == x:
            return [[c]]

        if pow(c, n) > x:
            return []

        l = helper(x, n, c + 1)
        r = helper(x - pow(c, n), n, c + 1)

        for _r in r:
            l.append([c] + _r)

        return l

    return helper(targetSum, N, 1)

print(powerSum(100, 2))

获取幂和问题的所有可能组合

Getting all possible combinations for powersum problem

python

recursion

dynamic-programming