Find out which combination of numbers in set add up to a given tơtal?

Question

I have set of numbers; example: [12, 13, 15, 18]. From which I have to find the elements whose sum is a specific "total value", for example: 25 is 12 + 13.

Edit: First of all thank you all for your valuable feedback but i think many of you misunderstood my question! My question is not just for "two combination" but for more than two. For example:

1 2 3 4 5 6 7 8 9 10 100

From the above list we need to get "119" here we need more than "two combination".

How can i write the code through bash script or JavaScript?

Kindly help.

you could get every combination, which is 2 ^ n and take the values by checking the sum. — Nina Scholz, Dec 24 '19 at 10:43
Why the downvote ? Question is 100% legit. Writing an answer now — Ki Jéy, Dec 24 '19 at 10:58
This might be helpful: https://stackoverflow.com/questions/4331092/finding-all-combinations-cartesian-product-of-javascript-array-values — bad_coder, Dec 24 '19 at 11:00
What have you tried so far to solve the problem? Are you looking for a solution in JavaScript or bash? — Cyrus, Dec 24 '19 at 11:30
JavaScript is good but bash is more preferable for me.I knew the both languages that's why i have mentioned above.Kindly guide me for more than "two combination"! Everyone misunderstood my question and gave the solutions regarding "two combination" but i would like to know more than three combination.For example: 1 2 3 4 5 and my "total value" is 10 — Saikat Mukherjee, Dec 24 '19 at 11:45

Nina Scholz · Answer 1 · 2019-12-24T12:13:45.360

4

You could take a recursive approach and check every combination by using a short circuit for sums wich are greater than the given sum.

function getSum(numbers, sum) {
    function iter(index, right, left) {
        if (!left) return result.push(right);
        if (left < 0 || index >= numbers.length) return;
        iter(index + 1, [...right, numbers[index]], left - numbers[index]);
        iter(index + 1, right, left);
    }

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

getSum([12, 13, 15, 18], 25).forEach(a => console.log(...a));
console.log('--')
getSum([1, 2, 3, 4, 5], 10).forEach(a => console.log(...a));

edited Dec 24 '19 at 12:13

answered Dec 24 '19 at 10:56

Nina Scholz

351,820
24
303
358

1

@Addis without the flat it allow to return every group which sum to the desired value, in the exemple there is only one so you can't see it, but try `getSum([12, 13, 18, 7], 25)` and you'll understand why flat must not be added – jonatjano Dec 24 '19 at 11:04

Pranav C Balan · Answer 2 · 2019-12-24T11:00:47.927

0

You can do something simple using indexOf method.

function findComb(arr, sum) {
  for (let i = 0; i < arr.length - 1; i++) {
    let j = arr.indexOf(sum - arr[i], i);
    if (j !== -1) {
      return [arr[i], arr[j]]
    }
  }
}

console.log(findComb([12, 13, 15, 18], 25))

Note : Will return only the first combination and limited to 2 numbers.

edited Dec 24 '19 at 11:00

answered Dec 24 '19 at 10:54

Pranav C Balan

110,383
23
155
178

1

Hmmm, I do not think the sum must be of two numbers only – Mafor Dec 24 '19 at 10:59
@Mafor : so i just added as note – Pranav C Balan Dec 24 '19 at 11:01

score 0 · Answer 3 · answered Dec 24 '19 at 10:55

0

let orgArr=[12,13,14,11,15,18];

orgArr.filter((each,i,orgArr)=>orgArr[i+1]!==undefined?each+orgArr[i+1]===25?console.log(each,"..",orgArr[i+1]):"":"")

it will give you the pair which sum is 25

answered Dec 24 '19 at 10:55

warmachine

366
1
6

what if you need three numbers to get up to 25 ? – jonatjano Dec 24 '19 at 11:02
Thank you all but what if the combination couldn't be possible in "two" variable and we need more than two combination to get the "total value"? – Saikat Mukherjee Dec 24 '19 at 11:21

score 0 · Answer 4 · answered Dec 24 '19 at 11:07

0

bash version:

#!/usr/bin/env bash

function find_sum {
    local sum=$1 first=$2; shift 2
    while test $# -gt 0; do
        for c; do
            if  test $sum = $(($first + $c)); then
                echo $sum = $first + $c
            fi
        done
        first=$1; shift
    done
}

find_sum 25 15 12 13 18

answered Dec 24 '19 at 11:07

Philippe

14,211
2
16
22

Can we do it for more than "two combination" ? – Saikat Mukherjee Dec 24 '19 at 12:24

Mafor · Answer 5 · 2019-12-24T11:51:55.767

0

It is a variant of the knapsack problem, try to google for it. You can find the solution recursively in 2^n, or in n^2 using two-dimensional array for storing partial results.

edited Dec 24 '19 at 11:51

answered Dec 24 '19 at 11:07

Mafor

7,598
1
12
22

score 0 · Answer 6 · answered Dec 24 '19 at 11:20

Find all combinations using indexOf and Set to stock unique values:

function findComb(total, arr) {
  const output = new Set([]);
  arr.forEach((el, index) => {
    const i = arr.indexOf(total - el, index);
    if(i > -1) { output.add(el); output.add(arr[i]); }
  });
  return [...output];
}
console.log(findComb(25, [12, 13, 15, 18]));
console.log(findComb(25, [12, 13, 7, 15, 18, 12]));

Find out which combination of numbers in set add up to a given tơtal?

6 Answers6