Идеальная сумма Проблема с повторениями

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

Я уже прошел соответствующие вопросы DP из https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/, https://www.geeksforgeeks.org/ways-sum-n-using-array-elements-repetition-allowed/ и , чтобы найти все подмножества, которые суммируются с определенным значением

Я не нашел способа или подсказки, как решить этот вопрос с разрешенными повторениями.Любые выводы будут полезны.

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

Answer 2

Сортируйте входной массив (если можете), а затем используйте https://en.wikipedia.org/wiki/Backtracking, чтобы получить все возможные решения.Просто перейдите к младшему числу и, если оно не может соответствовать, просто начните возвращаться и проверьте, может ли вместо этого подойти номер на один элемент выше (во входном массиве).