How can I create permutations to reach a target number, but reuse the provided numbers?

Question

EDIT:

var Combos = [1, 2, 4],
    Target = 4;

    for(var i = 0; i < Combos.length; i++){
        var Available = [];

        for(var j = -1; j < i; j++) Available.push(Combos[j+1]);
        for(var k = 0; k < Available.length; k++){
            var C = 0;
            var Att = 0;

            while(C < Target){ C += Available[k]; Att++; }
            if(C === Target) console.log(new Int8Array(Att).fill(Available[k]));
        }
    }

This outputs:

[1, 1, 1, 1]
[1, 1, 1, 1]
[2, 2]
[1, 1, 1, 1]
[2, 2]
[4]

I don't know why I'm getting the repetition of 1, 1, 1, 1 and 2, 2 but I'm investigating!

---

My provided numbers array will be [1, 2, 4], I'm trying to get to a target that will always fit; let's assume this is 4.

How can I return an array of combinations where the process reuses the provided numbers, for example: all of the questions I've looked at on here only use the numbers once, and thus these programs would return [[4]], whereas I'd like the result to be [[1, 1, 1, 1], [1, 1, 2], [2, 2], [4]].

At first, I thought about using modulus to say: is the target an integer, if so we can instantly return target / 1. But I honestly can't figure out the logic!

An IRC chat I've had, perhaps this might help you understand:

13:20   Robinlemon  So I have the numbers [1, 2] and I'm trying to make 4 so I want a function that will return [[1, 1, 1, 1], [1, 1 ,2], [2, 2], [4]] -> all the possible combinations to make the target, by reusing the numbers supplied
13:21   kakashiAL   how does your function api looks like?
13:21   Robinlemon  What do you mean?
13:21   Robinlemon  I've scrapped everything
13:21   kakashiAL   foo(myArray, combination=
13:21   Robinlemon  Because I can't ever work out the logic to do this
13:21   Robinlemon  Well I suppose i'd have
13:22   Robinlemon  Permutate(Price) => SubPermutate()
13:22   Robinlemon  Then return
13:22   Robinlemon  and tierate through each sub function
13:22   kakashiAL   so you have [1, 2] and you want to make 4, which means you want to have this:
13:22   kakashiAL   1, 1, 1, 1
13:22   kakashiAL   2, 2, 2, 2
13:23   kakashiAL   1, 2, 2, 2
13:23   kakashiAL   1, 1, 2, 2
13:23   kakashiAL   and so on
13:23   kakashiAL   right?
13:26   Robinlemon  yep
13:26   Robinlemon  well no
13:26   Robinlemon  The numbers need to add to 4
13:26   Robinlemon  so it wouldnt be 1, 1, 2, 2
13:26   Robinlemon  it would be 1 1 2
13:26   Robinlemon  get it
13:26   kakashiAL   you have the numbers 1, 2 and 4, correct?
13:28   Robinlemon  yes
13:28   Robinlemon  For example sake
13:29   Robinlemon  It should work with anything tho
13:29   Robinlemon  The target will always be reachable with the numbers
13:29   kakashiAL   okay, now you want to get this, with 1, 2 and 4:
13:29   kakashiAL   1, 1, 1
13:29   kakashiAL   2, 2, 2
13:29   kakashiAL   4, 4, 4
13:29   kakashiAL   1, 2, 4
13:29   kakashiAL   1, 1, 2
13:29   Robinlemon  No
13:29   Robinlemon  1, 1, 1, 1
13:29   Robinlemon  2, 2
13:29   Robinlemon  4
13:30   Robinlemon  The numbers need to add to 4
13:30   Robinlemon  I wnat the combinations that add to 4
13:30   kakashiAL   ahh if you have 6 you would have this:
13:30   kakashiAL   1, 1, 1, 1, 1, 1
13:30   kakashiAL   2, 2, 2
13:30   Robinlemon  Yes

Thanks for reading, I look forward to looking at your replies!

Answer 1

You could use a recursive approach with some exit conditions with checking the sum or the index.

Otherwise take the actual element and concat it to the temporary object and call the function again, without incrementing the index.

The other direction is to call the function again with an incremented index.

function getCombinations(array, sum) {

    function fork(i, t) {
        var s = t.reduce(function (a, b) { return a + b; }, 0);
        if (sum === s) {
            result.push(t);
            return;
        }
        if (s > sum || i === array.length) {
            return;
        }
        fork(i, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

console.log(getCombinations([1, 2, 4], 4));
console.log(getCombinations([0.11, 0.33, 1], 26.66));
console.log(getCombinations([0.11, 0.33, 1], 23.33));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Single use of a number

function getCombinations(array, sum) {

    function fork(i, t) {
        var s = t.reduce(function (a, b) { return a + b; }, 0);
        if (sum === s) {
            result.push(t);
            return;
        }
        if (s > sum || i === array.length) {
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

console.log(getCombinations([1, 2, 4], 4));
console.log(getCombinations([0.11, 0.33, 1], 26.66));
console.log(getCombinations([0.11, 0.33, 1], 23.33));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

This is a typical dynamical programming case question which most likely turns out to be a more efficient way to solve compared to other methods. Here is a non recursive dynamical programming solution.

function getCombos(a,t){
  var h = {},
    len = a.length,
      n = 0;

  for (var i = 0; i < len; i++){
    n = a[i];
    h[n] ? h[n].push([n]) : h[n] = [[n]];
    for(var j = a[0]; j <= t; j++){
      h[j] && (h[j+n] = h[j+n] ? h[j+n].concat(h[j].map(s => s.concat(n)))
                               : h[j].map(s => s.concat(n)));
    }
  }
  return h[t] || [];
}

var result = [];
console.time("dp for [1,2,4] to sum 4");
result = getCombos([1,2,4],4);
console.timeEnd("dp for [1,2,4] to sum 4");
console.log(JSON.stringify(result));

console.time("dp for [1,5,9] to sum 500");
result = getCombos([1,5,9],500);
console.timeEnd("dp for [1,5,9] to sum 500");
console.log("There are", result.length, "solutions");

Well as per your second request. To reach the target without repeating the items can also be done by above code however it would be terribly inefficient.

Such as giving [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20] and asking for the numbers to give the sum 210 (sum of all numbers) would take time until it crashes your browser.

The proper way of doing the reaching target sum by non-repetitive use of the array items is as follows;

function getSummingItems(a,t){
  return a.reduce((h,n) => Object.keys(h)
                                 .reduceRight((m,k) => +k+n <= t ? (m[+k+n] = m[+k+n] ? m[+k+n].concat(m[k].map(sa => sa.concat(n)))
                                                                                      : m[k].map(sa => sa.concat(n)),m)
                                                                 :  m, h), {0:[[]]})[t];
}
var arr = Array(20).fill().map((_,i) => i+1),
    tgt = 210,
    res = [];

console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log(res);

It will finalize the above calculation in less than 1 second. In order to boost the performance a little more one can replace the .reduce() and .reduceRight() with their imperative equivalents. Other than that, this is as fast as it gets from me.