Python Decompose number函数接收数字和分解方法

Question

我正在尝试创建一个仅使用给定数字分解数字的函数:

比如要分解的数是5，分解的方式有1,2,5

def func(Number_to_decompose,list_with posible_ways_to_decompose)
func(5,[1,2,5])

所以函数应该返回:

[[1,1,1,1,1],[2,1,1,1],[1,2,1,1],[1,1,2,1],[1,1,1,2],[5]]

考虑到列表中的数字正在添加所以 [1+1+1+2] 是 5!

Answer 1

这有一个非常自然的递归公式:

from copy import copy
def recurse_find(decomposed,remaining,valid_numbers):
    #base case
    if remaining == 0:
        return decomposed
    #find all valid subtractions
    else:
        ans = []
        for number in valid_numbers:
            if remaining - number >= 0:
                new_decomposed = copy(decomposed)
                new_decomposed.append(number)
                cand = recurse_find(new_decomposed,remaining- 
                              number,valid_numbers)
                if cand:
                    ans.append(cand)
        if len(ans) > 0:
            return ans

print(recurse_find([],5,[1,2,5])) --> 匹配您请求的输出。