0

Let's say I have a set number like 9 and an array that has #s [1,2,4,6,3,9]. I was wondering what would be the best approach to loop through and see if one or more of those #s can add up to 9. My initial thought was to:

  • Check if the current array index value is equal to the magicNum
  • If the current number is less than the magicNum, add it together with another number in the array and keep looping to see if it's a match
  • If the above didn't work, move to the next number and repeat.

I have the first check fine but it's the other two I'm having trouble with. I know for starters that a recursive function may (or may not) be needed in addition to using reduce. Algorithms aren't my strong suit (yet) but I'm eager and more than willing to improve. Any type of guidance would be greatly appreciated.

const magicNum = 9;

const arr = [10,1,2,4,6,3];

for (let i = 0, arrLength = arr.length; i < arrLength; i++) {
  if (arr[i] === magicNum) {
    console.log('Number Found!');
    continue;
  } else if (arr[i] > magicNum) {
    continue;
  } else if (arr[i] < magicNum) {
    // Stuck here
  }
}
Carl Edwards
  • 13,826
  • 11
  • 57
  • 119
  • The second condition isn't clear, what are you expecting there? Do you mean that, if it's less, future iterations will also try to find `magicNum + ` rather than just `magicNum`? – CertainPerformance Aug 17 '18 at 08:28
  • is 9 the magic number? what is a magical number? what has it to do for adding some numbers, if you look for a number, which could be more then one in the array. why break, if not at the end of the array? please add the result of the second (where the 9 is missing). – Nina Scholz Aug 17 '18 at 08:28
  • Why not just use `.includes`? No need to write your own function – CertainPerformance Aug 17 '18 at 08:31
  • 1. You don't need 'continue' while using else if statements. 2. Can you show a test case? What happens? The question isn't quite clear. – Sivcan Singh Aug 17 '18 at 08:31
  • @CertainPerformance For the second condition, let's say the current index value is 1. Obviously that wouldn't be equal to 9 so see if there's any other numbers in the array that you can add to 1 in order to equal 9. If not continue on to the next number in the array and repeat. – Carl Edwards Aug 17 '18 at 08:34
  • Which other number do you want to add it to? the next one, or any of them? – Nick Aug 17 '18 at 08:35
  • @NinaScholz `magicNum` is just the name I gave to the target number. You're right. I revised the code so that it `continues` vs. breaking. – Carl Edwards Aug 17 '18 at 08:36
  • @CarlEdwards So you always need a pair of numbers to equal the magic number? Or all possibilites that add upto 9? – Sivcan Singh Aug 17 '18 at 08:36
  • `arr.includes(9)` will return a Boolean that tells you whether `arr` includes `9`. – CertainPerformance Aug 17 '18 at 08:37
  • @CertainPerformance The thing is I also need to know if two or more #s in the array can add up to the # 9. – Carl Edwards Aug 17 '18 at 08:38
  • 1
    You should put that in your question - as it stands, it's quite unclear – CertainPerformance Aug 17 '18 at 08:40
  • I thought the original title: "Finding if one ore more numbers in an array are equal to a certain number" would have been enough but revised that and the description in hopes to better understand. – Carl Edwards Aug 17 '18 at 08:43
  • Duplicate of https://stackoverflow.com/questions/18305843/find-all-subsets-that-sum-to-a-particular-value bro – Sivcan Singh Aug 17 '18 at 08:53
  • Did you scroll down? @Redu has answered it using Javascript. – Sivcan Singh Aug 17 '18 at 08:56
  • @CarlEdwards Added the solution to my answer. – Sivcan Singh Aug 17 '18 at 08:57

2 Answers2

1

You could take an iterative and recursive approach for finding subset sums.

function getSubsets(array, sum) {

    function fork(i = 0, s = 0, t = []) {
        if (s === sum) {
            result.push(t);
            return;
        }
        if (i === array.length) {
            return;
        }
        if (s + array[i] <= sum) { // shout circuit for positive numbers only
            fork(i + 1, s + array[i], t.concat(array[i]));
        }
        fork(i + 1, s, t);
    }

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

console.log(getSubsets([10, 1, 2, 4, 6, 3], 9));
.as-console-wrapper { max-height: 100% !important; top: 0; }

For getting only the first subset, you might exit the recursion with the first found array of values.

function getFirstSubset(array, sum) {

    function fork(i = 0, s = 0, t = []) {
        if (s === sum) {
            return  t;
        }
        if (i === array.length) {
            return;
        }
        return fork(i + 1, s + array[i], t.concat(array[i]))
            || fork(i + 1, s, t);
    }

    return fork();
}

console.log(getFirstSubset([10, 1, 2, 4, 6, 3], 9));
.as-console-wrapper { max-height: 100% !important; top: 0; }
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
0

This is more of a dynamic programming question. You can refer the following to achieve this: https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/

What you actually need is to list all the subsets of the array whose sum of digits is equal to the given magic number.

EDIT: Duplicate of find all subsets that sum to a particular value

Posting @Redu's answer from the above post:

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), // [1,2,..,20]
    tgt = 9,
    res = [];

console.time("test");
res = getSummingItems(arr,tgt);
console.timeEnd("test");
console.log("found",res.length,"subsequences summing to",tgt);
console.log(JSON.stringify(res));
Sivcan Singh
  • 1,775
  • 11
  • 15