To find minimum elements in array which has sum equals to given value Unicorn Meta Zoo #1: Why another podcast? Announcing the arrival of Valued Associate #679: Cesar Manara Data science time! April 2019 and salary with experience The Ask Question Wizard is Live!Find all possible subset combos in an array?Get the sum of array items that are equal to the target (Subset sum)Return all subsets whose sum is a given value (subset sum problem)Which “href” value should I use for JavaScript links, “#” or “javascript:void(0)”?Which equals operator (== vs ===) should be used in JavaScript comparisons?PHP: Delete an element from an arrayDeleting array elements in JavaScript - delete vs spliceHow do I determine whether an array contains a particular value in Java?Sort array of objects by string property valueDetermine whether an array contains a valueHow do I remove a particular element from an array in JavaScript?Copy array by valueHow can I add new array elements at the beginning of an array in Javascript?

How to open locks without disable device?

Why did C use the -> operator instead of reusing the . operator?

Is there any hidden 'W' sound after 'comment' in : Comment est-elle?

How to keep bees out of canned beverages?

How can I wire a 9-position switch so that each position turns on one more LED than the one before?

Do I need to protect SFP ports and optics from dust/contaminants? If so, how?

Expansion//Explosion and Siren Stormtamer

What do you call the part of a novel that is not dialog?

Multiple options vs single option UI

Seek and ye shall find

Passing args from the bash script to the function in the script

Would reducing the reference voltage of an ADC have any effect on accuracy?

Is it OK if I do not take the receipt in Germany?

What is the least dense liquid under normal conditions?

France's Public Holidays' Puzzle

How do I check if a string is entirely made of the same substring?

Retract an already submitted recommendation letter (written for an undergrad student)

Can I criticise the more senior developers around me for not writing clean code?

What is it called when you ride around on your front wheel?

Where did Arya get these scars?

As an international instructor, should I openly talk about my accent?

What ability score does a Hexblade's Pact Weapon use for attack and damage when wielded by another character?

What *exactly* is electrical current, voltage, and resistance?

How to use @AuraEnabled base class method in Lightning Component?



To find minimum elements in array which has sum equals to given value



Unicorn Meta Zoo #1: Why another podcast?
Announcing the arrival of Valued Associate #679: Cesar Manara
Data science time! April 2019 and salary with experience
The Ask Question Wizard is Live!Find all possible subset combos in an array?Get the sum of array items that are equal to the target (Subset sum)Return all subsets whose sum is a given value (subset sum problem)Which “href” value should I use for JavaScript links, “#” or “javascript:void(0)”?Which equals operator (== vs ===) should be used in JavaScript comparisons?PHP: Delete an element from an arrayDeleting array elements in JavaScript - delete vs spliceHow do I determine whether an array contains a particular value in Java?Sort array of objects by string property valueDetermine whether an array contains a valueHow do I remove a particular element from an array in JavaScript?Copy array by valueHow can I add new array elements at the beginning of an array in Javascript?



.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;








7















I am trying to find out the minimum elements in array whose sum equals
the given input.I tried for few input sum but was able to find only a
pair in first case while I need to implement for more than just a pair.






var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b)
return a - b;
);
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize)

if (arr[l] + arr[arrSize] === sum)
var result = newArr.concat(arr[l], arr[arrSize]);
console.log(result);
break;
else if (arr[l] + arr[arrSize] > sum)
arrSize--;
else
l++;







Input Array : [10, 0, -1, 20, 25, 30]



Required Sum: 45



Output: [20, 25]




I am trying for




Required Sum : 59



Output: [10, -1, 20, 30]











share|improve this question



















  • 1





    It's a Subset sum problem. You can search for "Subset sum problem javascript". There are many implementations like: Return all subsets whose sum is a given value (subset sum problem) and Get the sum of array items that are equal to the target (Subset sum)

    – adiga
    Apr 20 at 6:43


















7















I am trying to find out the minimum elements in array whose sum equals
the given input.I tried for few input sum but was able to find only a
pair in first case while I need to implement for more than just a pair.






var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b)
return a - b;
);
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize)

if (arr[l] + arr[arrSize] === sum)
var result = newArr.concat(arr[l], arr[arrSize]);
console.log(result);
break;
else if (arr[l] + arr[arrSize] > sum)
arrSize--;
else
l++;







Input Array : [10, 0, -1, 20, 25, 30]



Required Sum: 45



Output: [20, 25]




I am trying for




Required Sum : 59



Output: [10, -1, 20, 30]











share|improve this question



















  • 1





    It's a Subset sum problem. You can search for "Subset sum problem javascript". There are many implementations like: Return all subsets whose sum is a given value (subset sum problem) and Get the sum of array items that are equal to the target (Subset sum)

    – adiga
    Apr 20 at 6:43














7












7








7


2






I am trying to find out the minimum elements in array whose sum equals
the given input.I tried for few input sum but was able to find only a
pair in first case while I need to implement for more than just a pair.






var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b)
return a - b;
);
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize)

if (arr[l] + arr[arrSize] === sum)
var result = newArr.concat(arr[l], arr[arrSize]);
console.log(result);
break;
else if (arr[l] + arr[arrSize] > sum)
arrSize--;
else
l++;







Input Array : [10, 0, -1, 20, 25, 30]



Required Sum: 45



Output: [20, 25]




I am trying for




Required Sum : 59



Output: [10, -1, 20, 30]











share|improve this question
















I am trying to find out the minimum elements in array whose sum equals
the given input.I tried for few input sum but was able to find only a
pair in first case while I need to implement for more than just a pair.






var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b)
return a - b;
);
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize)

if (arr[l] + arr[arrSize] === sum)
var result = newArr.concat(arr[l], arr[arrSize]);
console.log(result);
break;
else if (arr[l] + arr[arrSize] > sum)
arrSize--;
else
l++;







Input Array : [10, 0, -1, 20, 25, 30]



Required Sum: 45



Output: [20, 25]




I am trying for




Required Sum : 59



Output: [10, -1, 20, 30]







var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b)
return a - b;
);
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize)

if (arr[l] + arr[arrSize] === sum)
var result = newArr.concat(arr[l], arr[arrSize]);
console.log(result);
break;
else if (arr[l] + arr[arrSize] > sum)
arrSize--;
else
l++;






var arr = [10, 0, -1, 20, 25, 30];
var sum = 45;
var newArr = [];
console.log('before sorting = ' + arr);

arr.sort(function(a, b)
return a - b;
);
console.log('after sorting = ' + arr);

var l = 0;
var arrSize = arr.length - 1;

while (l < arrSize)

if (arr[l] + arr[arrSize] === sum)
var result = newArr.concat(arr[l], arr[arrSize]);
console.log(result);
break;
else if (arr[l] + arr[arrSize] > sum)
arrSize--;
else
l++;







javascript arrays sorting






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Apr 20 at 6:25









Eddie

20.7k51742




20.7k51742










asked Apr 20 at 6:24









Abhishek KonnurAbhishek Konnur

12811




12811







  • 1





    It's a Subset sum problem. You can search for "Subset sum problem javascript". There are many implementations like: Return all subsets whose sum is a given value (subset sum problem) and Get the sum of array items that are equal to the target (Subset sum)

    – adiga
    Apr 20 at 6:43













  • 1





    It's a Subset sum problem. You can search for "Subset sum problem javascript". There are many implementations like: Return all subsets whose sum is a given value (subset sum problem) and Get the sum of array items that are equal to the target (Subset sum)

    – adiga
    Apr 20 at 6:43








1




1





It's a Subset sum problem. You can search for "Subset sum problem javascript". There are many implementations like: Return all subsets whose sum is a given value (subset sum problem) and Get the sum of array items that are equal to the target (Subset sum)

– adiga
Apr 20 at 6:43






It's a Subset sum problem. You can search for "Subset sum problem javascript". There are many implementations like: Return all subsets whose sum is a given value (subset sum problem) and Get the sum of array items that are equal to the target (Subset sum)

– adiga
Apr 20 at 6:43













4 Answers
4






active

oldest

votes


















3














One option is to find all possible subsets of the array, and then filter them by those which sum to the required value, and then identify the one(s) with the lowest length:






const getMinElementsWhichSum = (arr, target) => 
const subsets = getAllSubsetsOfArr(arr);
const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, length: Infinity );
;
console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

// https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
function getAllSubsetsOfArr(array)
return new Array(1 << array.length).fill().map(
(e1,i) => array.filter((e2, j) => i & 1 << j));








share|improve this answer

























  • let me try with this logic

    – Abhishek Konnur
    Apr 20 at 6:41


















2














This can be viewed as an optimization problem which lends itself well to dynamic programming.



This means you would break it up into a recursion that tries to find the minimum length of increasingly smaller arrays with the sum adjusted for what's been removed. It you array is [10, 0, -1, 20, 25, 30] with a sum of 59 you can think of shortest as the min of:



[10, ... shortest([ 0, -1, 20, 25, 30], 49)
[0, ... shortest([10, 20, 25, 30], 49), 59)
[-1, ... shortest([10, 0, 20, 25, 30], 60)
... continue recursively


with each recursion it the array gets shorter until you are left with one element then the question is just if that element equals the number left over after all the subtractions.



It's easier to show in code:






function findMinSum(arr, n)
if(!arr) return
let min
for (let i=0; i<arr.length; i++)

/* if a number equals the sum, it's obviously
* the shortest set, just return it
*/
if (arr[i] == n) return [arr[i]]

/* recursively call on subset with
* sum adjusted for removed element
*/
let next = findMinSum(arr.slice(i+1), n-arr[i])

/* we only care about next if it's shorter then
* the shortest thing we've seen so far
*/
if (next) next.length < min.length)
min = [arr[i], ...next]



return min && min /* if we found a match return it, otherwise return undefined */


console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum





This is still pretty computational expensive, but it should be much faster than finding all the subsets and sums.






share|improve this answer
































    0














    Try this,






    var arr = [10, 0, -1, 20, 25, 30];
    var sum = 29;
    var newArr = [];
    var sum_expected = 0;
    var y = 0;
    while (y < arr.length)
    for (let i = 0; i < arr.length; i++)
    var subArr = [];
    sum_expected = arr[i];
    if (arr[i] != 0) subArr.push(arr[i]);
    for (let j = 0; j < arr.length; j++)
    if (i == j)
    continue;
    sum_expected += arr[j];
    if (arr[j] != 0) subArr.push(arr[j]);
    if (sum_expected == sum)
    var result = arr.filter((el)=>(subArr.indexOf(el) > -1));
    !newArr.length ? newArr = result : result.length < newArr.length ? newArr = result : 1;
    break;



    let x = arr.shift();
    arr.push(x);
    y++;

    if (newArr.length)
    console.log(newArr);
    else
    console.log('Not found');








    share|improve this answer




















    • 1





      @MarkMeyer Fixed Thanks!

      – Shoyeb Sheikh
      Apr 20 at 8:04


















    0














    Try BFS (Breath First Search) algorithym
    https://en.wikipedia.org/wiki/Breadth-first_search






    share|improve this answer










    New contributor




    Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.




















      Your Answer






      StackExchange.ifUsing("editor", function ()
      StackExchange.using("externalEditor", function ()
      StackExchange.using("snippets", function ()
      StackExchange.snippets.init();
      );
      );
      , "code-snippets");

      StackExchange.ready(function()
      var channelOptions =
      tags: "".split(" "),
      id: "1"
      ;
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function()
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled)
      StackExchange.using("snippets", function()
      createEditor();
      );

      else
      createEditor();

      );

      function createEditor()
      StackExchange.prepareEditor(
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader:
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      ,
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      );



      );













      draft saved

      draft discarded


















      StackExchange.ready(
      function ()
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55770891%2fto-find-minimum-elements-in-array-which-has-sum-equals-to-given-value%23new-answer', 'question_page');

      );

      Post as a guest















      Required, but never shown

























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      3














      One option is to find all possible subsets of the array, and then filter them by those which sum to the required value, and then identify the one(s) with the lowest length:






      const getMinElementsWhichSum = (arr, target) => 
      const subsets = getAllSubsetsOfArr(arr);
      const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
      return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, length: Infinity );
      ;
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

      // https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
      function getAllSubsetsOfArr(array)
      return new Array(1 << array.length).fill().map(
      (e1,i) => array.filter((e2, j) => i & 1 << j));








      share|improve this answer

























      • let me try with this logic

        – Abhishek Konnur
        Apr 20 at 6:41















      3














      One option is to find all possible subsets of the array, and then filter them by those which sum to the required value, and then identify the one(s) with the lowest length:






      const getMinElementsWhichSum = (arr, target) => 
      const subsets = getAllSubsetsOfArr(arr);
      const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
      return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, length: Infinity );
      ;
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

      // https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
      function getAllSubsetsOfArr(array)
      return new Array(1 << array.length).fill().map(
      (e1,i) => array.filter((e2, j) => i & 1 << j));








      share|improve this answer

























      • let me try with this logic

        – Abhishek Konnur
        Apr 20 at 6:41













      3












      3








      3







      One option is to find all possible subsets of the array, and then filter them by those which sum to the required value, and then identify the one(s) with the lowest length:






      const getMinElementsWhichSum = (arr, target) => 
      const subsets = getAllSubsetsOfArr(arr);
      const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
      return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, length: Infinity );
      ;
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

      // https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
      function getAllSubsetsOfArr(array)
      return new Array(1 << array.length).fill().map(
      (e1,i) => array.filter((e2, j) => i & 1 << j));








      share|improve this answer















      One option is to find all possible subsets of the array, and then filter them by those which sum to the required value, and then identify the one(s) with the lowest length:






      const getMinElementsWhichSum = (arr, target) => 
      const subsets = getAllSubsetsOfArr(arr);
      const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
      return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, length: Infinity );
      ;
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

      // https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
      function getAllSubsetsOfArr(array)
      return new Array(1 << array.length).fill().map(
      (e1,i) => array.filter((e2, j) => i & 1 << j));








      const getMinElementsWhichSum = (arr, target) => 
      const subsets = getAllSubsetsOfArr(arr);
      const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
      return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, length: Infinity );
      ;
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

      // https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
      function getAllSubsetsOfArr(array)
      return new Array(1 << array.length).fill().map(
      (e1,i) => array.filter((e2, j) => i & 1 << j));





      const getMinElementsWhichSum = (arr, target) => 
      const subsets = getAllSubsetsOfArr(arr);
      const subsetsWhichSumToTarget = subsets.filter(subset => subset.reduce((a, b) => a + b, 0) === target);
      return subsetsWhichSumToTarget.reduce((a, b) => a.length < b.length ? a : b, length: Infinity );
      ;
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 45));
      console.log(getMinElementsWhichSum([10, 0, -1, 20, 25, 30], 59));

      // https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array
      function getAllSubsetsOfArr(array)
      return new Array(1 << array.length).fill().map(
      (e1,i) => array.filter((e2, j) => i & 1 << j));






      share|improve this answer














      share|improve this answer



      share|improve this answer








      edited Apr 20 at 6:42

























      answered Apr 20 at 6:36









      CertainPerformanceCertainPerformance

      102k166393




      102k166393












      • let me try with this logic

        – Abhishek Konnur
        Apr 20 at 6:41

















      • let me try with this logic

        – Abhishek Konnur
        Apr 20 at 6:41
















      let me try with this logic

      – Abhishek Konnur
      Apr 20 at 6:41





      let me try with this logic

      – Abhishek Konnur
      Apr 20 at 6:41













      2














      This can be viewed as an optimization problem which lends itself well to dynamic programming.



      This means you would break it up into a recursion that tries to find the minimum length of increasingly smaller arrays with the sum adjusted for what's been removed. It you array is [10, 0, -1, 20, 25, 30] with a sum of 59 you can think of shortest as the min of:



      [10, ... shortest([ 0, -1, 20, 25, 30], 49)
      [0, ... shortest([10, 20, 25, 30], 49), 59)
      [-1, ... shortest([10, 0, 20, 25, 30], 60)
      ... continue recursively


      with each recursion it the array gets shorter until you are left with one element then the question is just if that element equals the number left over after all the subtractions.



      It's easier to show in code:






      function findMinSum(arr, n)
      if(!arr) return
      let min
      for (let i=0; i<arr.length; i++)

      /* if a number equals the sum, it's obviously
      * the shortest set, just return it
      */
      if (arr[i] == n) return [arr[i]]

      /* recursively call on subset with
      * sum adjusted for removed element
      */
      let next = findMinSum(arr.slice(i+1), n-arr[i])

      /* we only care about next if it's shorter then
      * the shortest thing we've seen so far
      */
      if (next) next.length < min.length)
      min = [arr[i], ...next]



      return min && min /* if we found a match return it, otherwise return undefined */


      console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
      console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
      console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum





      This is still pretty computational expensive, but it should be much faster than finding all the subsets and sums.






      share|improve this answer





























        2














        This can be viewed as an optimization problem which lends itself well to dynamic programming.



        This means you would break it up into a recursion that tries to find the minimum length of increasingly smaller arrays with the sum adjusted for what's been removed. It you array is [10, 0, -1, 20, 25, 30] with a sum of 59 you can think of shortest as the min of:



        [10, ... shortest([ 0, -1, 20, 25, 30], 49)
        [0, ... shortest([10, 20, 25, 30], 49), 59)
        [-1, ... shortest([10, 0, 20, 25, 30], 60)
        ... continue recursively


        with each recursion it the array gets shorter until you are left with one element then the question is just if that element equals the number left over after all the subtractions.



        It's easier to show in code:






        function findMinSum(arr, n)
        if(!arr) return
        let min
        for (let i=0; i<arr.length; i++)

        /* if a number equals the sum, it's obviously
        * the shortest set, just return it
        */
        if (arr[i] == n) return [arr[i]]

        /* recursively call on subset with
        * sum adjusted for removed element
        */
        let next = findMinSum(arr.slice(i+1), n-arr[i])

        /* we only care about next if it's shorter then
        * the shortest thing we've seen so far
        */
        if (next) next.length < min.length)
        min = [arr[i], ...next]



        return min && min /* if we found a match return it, otherwise return undefined */


        console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
        console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
        console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum





        This is still pretty computational expensive, but it should be much faster than finding all the subsets and sums.






        share|improve this answer



























          2












          2








          2







          This can be viewed as an optimization problem which lends itself well to dynamic programming.



          This means you would break it up into a recursion that tries to find the minimum length of increasingly smaller arrays with the sum adjusted for what's been removed. It you array is [10, 0, -1, 20, 25, 30] with a sum of 59 you can think of shortest as the min of:



          [10, ... shortest([ 0, -1, 20, 25, 30], 49)
          [0, ... shortest([10, 20, 25, 30], 49), 59)
          [-1, ... shortest([10, 0, 20, 25, 30], 60)
          ... continue recursively


          with each recursion it the array gets shorter until you are left with one element then the question is just if that element equals the number left over after all the subtractions.



          It's easier to show in code:






          function findMinSum(arr, n)
          if(!arr) return
          let min
          for (let i=0; i<arr.length; i++)

          /* if a number equals the sum, it's obviously
          * the shortest set, just return it
          */
          if (arr[i] == n) return [arr[i]]

          /* recursively call on subset with
          * sum adjusted for removed element
          */
          let next = findMinSum(arr.slice(i+1), n-arr[i])

          /* we only care about next if it's shorter then
          * the shortest thing we've seen so far
          */
          if (next) next.length < min.length)
          min = [arr[i], ...next]



          return min && min /* if we found a match return it, otherwise return undefined */


          console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
          console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
          console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum





          This is still pretty computational expensive, but it should be much faster than finding all the subsets and sums.






          share|improve this answer















          This can be viewed as an optimization problem which lends itself well to dynamic programming.



          This means you would break it up into a recursion that tries to find the minimum length of increasingly smaller arrays with the sum adjusted for what's been removed. It you array is [10, 0, -1, 20, 25, 30] with a sum of 59 you can think of shortest as the min of:



          [10, ... shortest([ 0, -1, 20, 25, 30], 49)
          [0, ... shortest([10, 20, 25, 30], 49), 59)
          [-1, ... shortest([10, 0, 20, 25, 30], 60)
          ... continue recursively


          with each recursion it the array gets shorter until you are left with one element then the question is just if that element equals the number left over after all the subtractions.



          It's easier to show in code:






          function findMinSum(arr, n)
          if(!arr) return
          let min
          for (let i=0; i<arr.length; i++)

          /* if a number equals the sum, it's obviously
          * the shortest set, just return it
          */
          if (arr[i] == n) return [arr[i]]

          /* recursively call on subset with
          * sum adjusted for removed element
          */
          let next = findMinSum(arr.slice(i+1), n-arr[i])

          /* we only care about next if it's shorter then
          * the shortest thing we've seen so far
          */
          if (next) next.length < min.length)
          min = [arr[i], ...next]



          return min && min /* if we found a match return it, otherwise return undefined */


          console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
          console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
          console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum





          This is still pretty computational expensive, but it should be much faster than finding all the subsets and sums.






          function findMinSum(arr, n)
          if(!arr) return
          let min
          for (let i=0; i<arr.length; i++)

          /* if a number equals the sum, it's obviously
          * the shortest set, just return it
          */
          if (arr[i] == n) return [arr[i]]

          /* recursively call on subset with
          * sum adjusted for removed element
          */
          let next = findMinSum(arr.slice(i+1), n-arr[i])

          /* we only care about next if it's shorter then
          * the shortest thing we've seen so far
          */
          if (next) next.length < min.length)
          min = [arr[i], ...next]



          return min && min /* if we found a match return it, otherwise return undefined */


          console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
          console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
          console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum





          function findMinSum(arr, n)
          if(!arr) return
          let min
          for (let i=0; i<arr.length; i++)

          /* if a number equals the sum, it's obviously
          * the shortest set, just return it
          */
          if (arr[i] == n) return [arr[i]]

          /* recursively call on subset with
          * sum adjusted for removed element
          */
          let next = findMinSum(arr.slice(i+1), n-arr[i])

          /* we only care about next if it's shorter then
          * the shortest thing we've seen so far
          */
          if (next) next.length < min.length)
          min = [arr[i], ...next]



          return min && min /* if we found a match return it, otherwise return undefined */


          console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
          console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
          console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum






          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Apr 20 at 7:54

























          answered Apr 20 at 7:36









          Mark MeyerMark Meyer

          42k33665




          42k33665





















              0














              Try this,






              var arr = [10, 0, -1, 20, 25, 30];
              var sum = 29;
              var newArr = [];
              var sum_expected = 0;
              var y = 0;
              while (y < arr.length)
              for (let i = 0; i < arr.length; i++)
              var subArr = [];
              sum_expected = arr[i];
              if (arr[i] != 0) subArr.push(arr[i]);
              for (let j = 0; j < arr.length; j++)
              if (i == j)
              continue;
              sum_expected += arr[j];
              if (arr[j] != 0) subArr.push(arr[j]);
              if (sum_expected == sum)
              var result = arr.filter((el)=>(subArr.indexOf(el) > -1));
              !newArr.length ? newArr = result : result.length < newArr.length ? newArr = result : 1;
              break;



              let x = arr.shift();
              arr.push(x);
              y++;

              if (newArr.length)
              console.log(newArr);
              else
              console.log('Not found');








              share|improve this answer




















              • 1





                @MarkMeyer Fixed Thanks!

                – Shoyeb Sheikh
                Apr 20 at 8:04















              0














              Try this,






              var arr = [10, 0, -1, 20, 25, 30];
              var sum = 29;
              var newArr = [];
              var sum_expected = 0;
              var y = 0;
              while (y < arr.length)
              for (let i = 0; i < arr.length; i++)
              var subArr = [];
              sum_expected = arr[i];
              if (arr[i] != 0) subArr.push(arr[i]);
              for (let j = 0; j < arr.length; j++)
              if (i == j)
              continue;
              sum_expected += arr[j];
              if (arr[j] != 0) subArr.push(arr[j]);
              if (sum_expected == sum)
              var result = arr.filter((el)=>(subArr.indexOf(el) > -1));
              !newArr.length ? newArr = result : result.length < newArr.length ? newArr = result : 1;
              break;



              let x = arr.shift();
              arr.push(x);
              y++;

              if (newArr.length)
              console.log(newArr);
              else
              console.log('Not found');








              share|improve this answer




















              • 1





                @MarkMeyer Fixed Thanks!

                – Shoyeb Sheikh
                Apr 20 at 8:04













              0












              0








              0







              Try this,






              var arr = [10, 0, -1, 20, 25, 30];
              var sum = 29;
              var newArr = [];
              var sum_expected = 0;
              var y = 0;
              while (y < arr.length)
              for (let i = 0; i < arr.length; i++)
              var subArr = [];
              sum_expected = arr[i];
              if (arr[i] != 0) subArr.push(arr[i]);
              for (let j = 0; j < arr.length; j++)
              if (i == j)
              continue;
              sum_expected += arr[j];
              if (arr[j] != 0) subArr.push(arr[j]);
              if (sum_expected == sum)
              var result = arr.filter((el)=>(subArr.indexOf(el) > -1));
              !newArr.length ? newArr = result : result.length < newArr.length ? newArr = result : 1;
              break;



              let x = arr.shift();
              arr.push(x);
              y++;

              if (newArr.length)
              console.log(newArr);
              else
              console.log('Not found');








              share|improve this answer















              Try this,






              var arr = [10, 0, -1, 20, 25, 30];
              var sum = 29;
              var newArr = [];
              var sum_expected = 0;
              var y = 0;
              while (y < arr.length)
              for (let i = 0; i < arr.length; i++)
              var subArr = [];
              sum_expected = arr[i];
              if (arr[i] != 0) subArr.push(arr[i]);
              for (let j = 0; j < arr.length; j++)
              if (i == j)
              continue;
              sum_expected += arr[j];
              if (arr[j] != 0) subArr.push(arr[j]);
              if (sum_expected == sum)
              var result = arr.filter((el)=>(subArr.indexOf(el) > -1));
              !newArr.length ? newArr = result : result.length < newArr.length ? newArr = result : 1;
              break;



              let x = arr.shift();
              arr.push(x);
              y++;

              if (newArr.length)
              console.log(newArr);
              else
              console.log('Not found');








              var arr = [10, 0, -1, 20, 25, 30];
              var sum = 29;
              var newArr = [];
              var sum_expected = 0;
              var y = 0;
              while (y < arr.length)
              for (let i = 0; i < arr.length; i++)
              var subArr = [];
              sum_expected = arr[i];
              if (arr[i] != 0) subArr.push(arr[i]);
              for (let j = 0; j < arr.length; j++)
              if (i == j)
              continue;
              sum_expected += arr[j];
              if (arr[j] != 0) subArr.push(arr[j]);
              if (sum_expected == sum)
              var result = arr.filter((el)=>(subArr.indexOf(el) > -1));
              !newArr.length ? newArr = result : result.length < newArr.length ? newArr = result : 1;
              break;



              let x = arr.shift();
              arr.push(x);
              y++;

              if (newArr.length)
              console.log(newArr);
              else
              console.log('Not found');





              var arr = [10, 0, -1, 20, 25, 30];
              var sum = 29;
              var newArr = [];
              var sum_expected = 0;
              var y = 0;
              while (y < arr.length)
              for (let i = 0; i < arr.length; i++)
              var subArr = [];
              sum_expected = arr[i];
              if (arr[i] != 0) subArr.push(arr[i]);
              for (let j = 0; j < arr.length; j++)
              if (i == j)
              continue;
              sum_expected += arr[j];
              if (arr[j] != 0) subArr.push(arr[j]);
              if (sum_expected == sum)
              var result = arr.filter((el)=>(subArr.indexOf(el) > -1));
              !newArr.length ? newArr = result : result.length < newArr.length ? newArr = result : 1;
              break;



              let x = arr.shift();
              arr.push(x);
              y++;

              if (newArr.length)
              console.log(newArr);
              else
              console.log('Not found');






              share|improve this answer














              share|improve this answer



              share|improve this answer








              edited Apr 20 at 8:20

























              answered Apr 20 at 7:29









              Shoyeb SheikhShoyeb Sheikh

              1,0681211




              1,0681211







              • 1





                @MarkMeyer Fixed Thanks!

                – Shoyeb Sheikh
                Apr 20 at 8:04












              • 1





                @MarkMeyer Fixed Thanks!

                – Shoyeb Sheikh
                Apr 20 at 8:04







              1




              1





              @MarkMeyer Fixed Thanks!

              – Shoyeb Sheikh
              Apr 20 at 8:04





              @MarkMeyer Fixed Thanks!

              – Shoyeb Sheikh
              Apr 20 at 8:04











              0














              Try BFS (Breath First Search) algorithym
              https://en.wikipedia.org/wiki/Breadth-first_search






              share|improve this answer










              New contributor




              Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
              Check out our Code of Conduct.
























                0














                Try BFS (Breath First Search) algorithym
                https://en.wikipedia.org/wiki/Breadth-first_search






                share|improve this answer










                New contributor




                Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                Check out our Code of Conduct.






















                  0












                  0








                  0







                  Try BFS (Breath First Search) algorithym
                  https://en.wikipedia.org/wiki/Breadth-first_search






                  share|improve this answer










                  New contributor




                  Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.










                  Try BFS (Breath First Search) algorithym
                  https://en.wikipedia.org/wiki/Breadth-first_search







                  share|improve this answer










                  New contributor




                  Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  share|improve this answer



                  share|improve this answer








                  edited Apr 20 at 8:40





















                  New contributor




                  Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.









                  answered Apr 20 at 8:30









                  Nguyễn Sanh Đình AnhNguyễn Sanh Đình Anh

                  584




                  584




                  New contributor




                  Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.





                  New contributor





                  Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.






                  Nguyễn Sanh Đình Anh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
                  Check out our Code of Conduct.



























                      draft saved

                      draft discarded
















































                      Thanks for contributing an answer to Stack Overflow!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid


                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.

                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function ()
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55770891%2fto-find-minimum-elements-in-array-which-has-sum-equals-to-given-value%23new-answer', 'question_page');

                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Sum ergo cogito? 1 nng

                      419 nièngy_Soadمي 19bal1.5o_g

                      Queiggey Chernihivv 9NnOo i Zw X QqKk LpB