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/的相关DP问题, https://www.geeksforgeeks.org/ways-sum-n-using-array-elements-repetition-allowed/和 find all subsets that sum to a particular value

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

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)));