5

This variable x contains a number that needs to be tested against an array. var x = 10; var ary = [ 3,5 ]

I want to test if x can be made up by the sum of any combination of the keys in ary, then show what keys do add up to make x.

In this case the 3 cannot be used. So the result would = 5, 5 if x = 10 ( because the function should search the array and find that 5 + 5 equals 10 )

The length of the array and x are not known. I'm not using any libraries. This is how far I've come thus far:

var x = 10;
var ary = [ 3, 5 ];

function cycle(){
  var result;
  for( var i = 0; i < ary.length; i++ ){
    if( ary[ i ] + ary[ i ] == x ){
       result = ary[ i ] + ',' + ary[ i ];
    }
    else if( ary[ i ] + ary[ i + 1 ] == x ){
      result = ary[ i ] + ',' + ary[ i + 1 ];
    }
    else if( ary[ i + 1 ] + ary[ i + 1 ] == x ){
      result = ary[ i + 1 ] + ',' + ary[ i + 1 ];
  }
  return result;
  }
}
  

var result = cycle();
document.write( result );

I know the above code is terrible, not flexible in the least, and only works in that particular case I use it for. How would I include all possible combinations?

Assuming the array still only has the 2 values 3 and 5, here are more examples how what result would get based on x:

if x = 8, result would = 3, 5;

if x = 15, result would = 5, 5, 5

if x = 9, result would = 3, 3, 3 etc.

Note: There should be no limit to how many times a key can be used.

  • Why is the same index added to itself at `ary[ i ] + ary[ i ] == x`? – guest271314 Oct 25 '16 at 16:01
  • @guest271314 The goal was to check to see if any sums add up to x. Including adding indexes to itself however many times to get x. Or adding it to any other index plus itself to get x. –  Oct 25 '16 at 16:03
  • 1
    Partition of number algorithm can help you http://stackoverflow.com/questions/400794/generating-the-partitions-of-a-number – Pardeep Dhingra Oct 25 '16 at 16:04
  • @PardeepDhingra Thank you. That example doesn't restrict the number of partitions to the keys of an array but I will try to see if it helps me come up with anything. –  Oct 25 '16 at 16:08
  • Possible duplicate of [How do I generate integer partitions?](http://stackoverflow.com/questions/1490001/how-do-i-generate-integer-partitions) – Dexygen Oct 25 '16 at 18:15
  • @GeorgeJempty Would consider linked Question to be a duplicate of present Question, where OP put forth effort to solve own Question. – guest271314 Oct 25 '16 at 18:21
  • @GeorgeJempty What is intrinsic value of "more"? Note also, fwiw, linked Question is not tagged `javascript`, `arrays`, present Question is not tagged `algorithm`, `combinations`. – guest271314 Oct 25 '16 at 18:31

1 Answers1

2

You can use multiplication. Create an array having .length equal to the greatest number within input array ary plus 1, multiply the index of the array by the current number, if the product equals target number, create an array having .length equal to index and fill the array with current element of ary, else set resulting index of returned array to input number.

const x = [8, 9, 10, 15];
let ary = [3, 5];

let nums = (n, arr) => {
  let [keys, res] = [
    Array.from(Array(Math.max.apply(Math, arr) + 1).keys()).splice(1)
    , Array()
  ];
  for (let prop of arr) {
    for (let index of keys) {
      if (prop * index <= n) {
        if (prop * index === n) {
          res.push(Array(index).fill(prop)); break;
        }
      } else {
        res.push(prop); break;
      }
    }
  }
  return {x:n, result:res};
}

for (let num of x) console.log(nums(num, ary));
guest271314
  • 1
  • 15
  • 104
  • 177
  • Thanks for your answer. This is a way better start than I had. The only problem is when I keep changing the value of `x` the function isn't consistent with what I'm looking for. For example when `x = 15` the result is `5, 5` where `5, 5, 5` is desired. I will study this and try to tweak it. Thanks. –  Oct 25 '16 at 17:09