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;
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]
javascript arrays sorting
add a comment |
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]
javascript arrays sorting
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
add a comment |
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]
javascript arrays sorting
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
javascript arrays sorting
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
add a comment |
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
add a comment |
4 Answers
4
active
oldest
votes
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));
let me try with this logic
– Abhishek Konnur
Apr 20 at 6:41
add a comment |
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.
add a comment |
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');
1
@MarkMeyer Fixed Thanks!
– Shoyeb Sheikh
Apr 20 at 8:04
add a comment |
Try BFS (Breath First Search) algorithym
https://en.wikipedia.org/wiki/Breadth-first_search
New contributor
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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));
let me try with this logic
– Abhishek Konnur
Apr 20 at 6:41
add a comment |
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));
let me try with this logic
– Abhishek Konnur
Apr 20 at 6:41
add a comment |
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));
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));
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
add a comment |
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
add a comment |
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.
add a comment |
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.
add a comment |
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.
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
edited Apr 20 at 7:54
answered Apr 20 at 7:36
Mark MeyerMark Meyer
42k33665
42k33665
add a comment |
add a comment |
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');
1
@MarkMeyer Fixed Thanks!
– Shoyeb Sheikh
Apr 20 at 8:04
add a comment |
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');
1
@MarkMeyer Fixed Thanks!
– Shoyeb Sheikh
Apr 20 at 8:04
add a comment |
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');
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');
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
add a comment |
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
add a comment |
Try BFS (Breath First Search) algorithym
https://en.wikipedia.org/wiki/Breadth-first_search
New contributor
add a comment |
Try BFS (Breath First Search) algorithym
https://en.wikipedia.org/wiki/Breadth-first_search
New contributor
add a comment |
Try BFS (Breath First Search) algorithym
https://en.wikipedia.org/wiki/Breadth-first_search
New contributor
Try BFS (Breath First Search) algorithym
https://en.wikipedia.org/wiki/Breadth-first_search
New contributor
edited Apr 20 at 8:40
New contributor
answered Apr 20 at 8:30
Nguyễn Sanh Đình AnhNguyễn Sanh Đình Anh
584
584
New contributor
New contributor
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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