python之如何打印所有组合 N 可以写成 1、3 和 4 的总和

我需要打印出数字 N 可以表示为 1、3、4 之和的不同方式。

例如 n=5:

• 1 + 1 + 1 + 1 + 1
• 1 + 4
• 4 + 1
• 1 + 1 + 3
• 1 + 3 + 1
• 3 + 1 + 1

我正在使用动态规划解决方案来寻找 n 可以写成 1,3,4 之和的可能方式的数量

 
    for i in range(4, n + 1):  
        DP[i] = DP[i - 1] + DP[i - 3] + DP[i - 4]  
 
    return DP[n] 
 

这有效，我得到了 N 可以表达的可能方式的数量，在这种情况下为 6，但我不确定如何打印出所有不同的方式:

• 1 + 1 + 1 + 1 + 1
• 1 + 4
• 4 + 1
• 1 + 1 + 3
• 1 + 3 + 1
• 3 + 1 + 1

非常欢迎任何建议，谢谢!

请您参考如下方法:

此递归生成器将生成实际组合:

def combis(n): 
    if n < 0: 
        return 
    if n == 0: 
        yield [] 
    for x in (1, 3, 4): 
        for combi in combis(n-x): 
            yield [x] + combi 
 
>>> list(combis(5)) 
[[1, 1, 1, 1, 1], [1, 1, 3], [1, 3, 1], [1, 4], [3, 1, 1], [4, 1]] 

当然，这不是 DP，而是一个简单的未缓存且性能不佳的递归实现。但它应该为 DP 解决方案指明方向。