arrays - 允许重复的完美和问题

Question

给定一个整数数组和一个总和，任务是打印给定数组的所有子集，其中总和等于给定总和，允许重复。

例子 ：

输入：arr = {1, 5, 6}, N = 7

输出：
1 1 1 1 1 1 1
1 1 5
1 5 1
5 1 1
1 6
6 1

我已经从https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/，https://www.geeksforgeeks.org/ways-sum-n-中完成了相关的 DP 问题using-array-elements-repetition-allowed/并找到总和为特定值的所有子集

我还没有找到关于如何在允许重复的情况下解决这个问题的方法或任何线索。任何线索都会有所帮助。

标签： arraysdynamic-programming

Answer 1

像这样的东西？

function f(A, N, r=[], s=N){
  if (s == 0)
    return [r];

  result = [];

  for (let a of A)
    if (a <= s)
      result = result.concat(
        f(A, N, r.slice().concat(a), s-a));

  return result;
}

console.log(JSON.stringify(f([1,5,6], 7)));