2

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.

jww
  • 97,681
  • 90
  • 411
  • 885
Saikat Mukherjee
  • 45
  • 2
  • 2
    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 – Mouradif 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

7 Answers7

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));
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
  • 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
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.

Pranav C Balan
  • 113,687
  • 23
  • 165
  • 188
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

warmachine
  • 376
  • 1
  • 8
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
Philippe
  • 20,025
  • 2
  • 23
  • 32
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.

Mafor
  • 9,668
  • 2
  • 21
  • 36
0

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]));
Fraction
  • 11,668
  • 5
  • 28
  • 48
0

I find a way to achieve the above question. I have used at the beginning the codes snippets above, but the problem with them is that they were failing when using very big numbers. The only limitation in my solution below that it's responding with only one result. However, running the code again, will most probably give another result.

My method below will work easily also with big numbers.

Give it a try.

var total = 0;
var transactions = [];

/**This is very important line, it limit the tries to a specific number, 
after that, it will consider no combinations**/
var limit_tries = 100000;


function shuffle (numbers){
    return numbers.sort((a, b) => 0.5 - Math.random());
}

function getSum(numbers, sum) {

    //Sorting the Array
    var newArray = numbers.sort((a, b) =>  a - b);
        
    //Print the Array After Cleaning
    
    while (total != sum && limit_tries > 0){
        for (var i=0;i<newArray.length;i++){
            if (total<sum){
                total = total + newArray[i];
                transactions.push(newArray[i]);
            }
        }

        if (total!=sum){
            transactions.length = 0;
            shuffle(newArray);
            total = 0;
            limit_tries = limit_tries - 1;
        } else if (total=sum){
            console.log (transactions);
            total= 0;
            transactions.length = 0;
            limit_tries = 1000000;
            break;
        }
    }
}

//Try 1 
getSum([5,1,22,55,12,34,22,12,54,6,5,23,1,2,6,8,22,45,23,33,15,65,12,90,12,7,8,9,1], 99);

//Try 2
getSum([5,1,22,55,12,34,22,12,54,6,5,23,1,2,6,8,22,45,23,33,15,65,12,90,12,7,8,9,1], 99);

//Try 3
getSum([5,1,22,55,12,34,22,12,54,6,5,23,1,2,6,8,22,45,23,33,15,65,12,90,12,7,8,9,1], 99);
ASammour
  • 865
  • 9
  • 12