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
  }
}

Improve this question
15
  • 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 + <foundNum> rather than just magicNum? Commented Aug 17, 2018 at 8: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). Commented Aug 17, 2018 at 8:28
  • Why not just use .includes? No need to write your own function Commented Aug 17, 2018 at 8: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. Commented Aug 17, 2018 at 8:31
  • 1
    You should put that in your question - as it stands, it's quite unclear Commented Aug 17, 2018 at 8:40

2 Answers 2

Reset to default
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; }

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

Your solution will only list the 'pairs'. There are more possibilities to achieve the magic number in the array. Basically a subset of the array is needed whose some of entries is equal to the magic Number.
He just answered @CertainPerformance with the following: @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 6 mins ago
@SivcanSingh, ok, i see.
Thanks @NinaScholz. Is there anyway to short circuit the function once one collection of numbers is found? That was my original intention. My apologies if I wasn't clear in my original question.
do you want to stop to search where it finds the first element? is this case it would return only [1, 2, 6].
|
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));
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.