Алгоритм размена монет
 

Нужно написать прогу которая считает сколькими способами можно разменяь какуе то квоту. Есть квота, есть монеты для размена и их количество, сделать нужно через backtracking .
то что я придумал выглядит примерно так, например есть
10(стоимсть монеты) 5 (количество)
7 3
8 3
1 7
с этого строю матрицу

var values = [
	[ 0, 10, 20, 30, 40, 50 ],
  [0, 7, 14, 21],
  [0, 8, 16, 24],
  [0, 1, 2, 3, 4, 5, 6, 7]
];

выглядит это примерно так

var count = (values, y, coinValue) => {
	if(y >= values.length)
  	return 0;
    
    var res = 0;
    
    for(var i = 0; i < values.length; i++) {
    	var v = coinValue - values[y][i];
      if(v === 0)
      	res++
      else if( v > 0) {
      		res+= count(values, y + 1, v);
      }
      else {
      	break;
      }
    }
    
    return res;
}

var values = [
	[ 0, 10, 20, 30, 40, 50 ],
  [0, 7, 14, 21],
  [0, 8, 16, 24],
  [0, 1, 2, 3, 4, 5, 6, 7]
];
var coinChangeValue = 55;
var res = 0;
for (var i = 0; i < values[0].length; i++) {
       var val = coinChangeValue - values[0][i];
       res += count(values, 1, val);
}

console.log(res);

Мне нужно как то оптимизировать сам алгоритм, потому что он слишком долго работает для больших чисел, гугли разные варианты, но как то не особо идет.
Может ктото подкинет идейку

какие то мелкие оптимизации не имею смысла код переписан с С++, я не могу оригинальный код вкинуть потому что система поиска плагиата меня отмыеет потом)) (это для универа).

cyber,

<script>

function combinator(matrix){
  return matrix.reduceRight(function(combination, x){
    var result = [];
    x.forEach(function(a){
      combination.forEach(function(b){
        result.push( [ a ].concat( b ) );
      });
    });
    return result;
  });
};
var arr = combinator([ [ 0, 10, 20, 30, 40, 50 ],[0, 7, 14, 21],[0, 8, 16, 24],[0, 1, 2, 3, 4, 5, 6, 7]] );
arr = arr.filter(function(a) {
  return 55 == a.reduce(function(a,b) {
   return a + b
})
})
document.write(
  arr.join("<br>")+ "<br>Всего вариантов : " + arr.length
);




</script>

рони, хм, а это идея, записать все возможные комбинации, а потом отфильровать, попробую, но мне кажется лимит по памяти не пройдет)
Спасибо за вариант, сейчас перепишу на С++))

cyber,
не знаю что выгоднее проверить все варианты один раз, или отсеивать по мере создания варианта, тогда вариантов в целом может быть меньше, но проверок больше каждого до 4 (в данном случае)

рони, не прошло, в 2 раза превысило лимит памяти

cyber,
тогда строить дерево ветка больше лимита отрезаем , ветка равна лимиту отрезаем в результат, меньше лимита оставляем и наращиваем.

cyber,
количество всех вариантов известно заранее 6 * 4 * 4 * 8 ... и не хранить все варианты а только верные результаты и четыре индекса.

рони, по сути больше проблема с временем работы чем с памятью, по сути при рекурсии я и так отбрасываю лишние и дальше не иду. Но еще по страдаю если не заработает то сделаю деревом, может так получится

cyber,
рекурсия кушает память как известно. может проще генерировать последовательно по одному и проверять подошёл не подошёл (это без оптимизации) ... 4 вложенных for c continue -- самый оптимальный вариант(для данного случая) ... понятно что нужен универсальный вариант.

да, я знаю, та версия алгоритма что у меня есть не проходит по времени по памяти норм, попробую еще раз на форах, если нет то перехожу к деревьям, хотя я реально не пойму как у некоторых одногрупников это заработало через рекурсию...