Find all subarray with sum equal to number? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Data science time! April 2019 and salary with experience The Ask Question Wizard is Live!Validate decimal numbers in JavaScript - IsNumeric()How can I format numbers as dollars currency string in JavaScript?Convert JavaScript String to be all lower case?Which equals operator (== vs ===) should be used in JavaScript comparisons?How to replace all occurrences of a string in JavaScriptHow to find the sum of an array of numbersGenerating random whole numbers in JavaScript in a specific range?How to print a number with commas as thousands separators in JavaScriptGenerate random number between two numbers in JavaScript
Why are the trig functions versine, haversine, exsecant, etc, rarely used in modern mathematics?
How to convince students of the implication truth values?
Crossing US/Canada Border for less than 24 hours
Around usage results
How could we fake a moon landing now?
Why do we bend a book to keep it straight?
Why aren't air breathing engines used as small first stages
Can melee weapons be used to deliver Contact Poisons?
Is there any way for the UK Prime Minister to make a motion directly dependent on Government confidence?
Is it fair for a professor to grade us on the possession of past papers?
Is it cost-effective to upgrade an old-ish Giant Escape R3 commuter bike with entry-level branded parts (wheels, drivetrain)?
Compare a given version number in the form major.minor.build.patch and see if one is less than the other
Can you use the Shield Master feat to shove someone before you make an attack by using a Readied action?
Is the Standard Deduction better than Itemized when both are the same amount?
Should I use a zero-interest credit card for a large one-time purchase?
How do I find out the mythology and history of my Fortress?
Can anything be seen from the center of the Boötes void? How dark would it be?
How to answer "Have you ever been terminated?"
What would be the ideal power source for a cybernetic eye?
Is it common practice to audition new musicians one-on-one before rehearsing with the entire band?
2001: A Space Odyssey's use of the song "Daisy Bell" (Bicycle Built for Two); life imitates art or vice-versa?
Do I really need to have a message in a novel to appeal to readers?
Amount of permutations on an NxNxN Rubik's Cube
How do I stop a creek from eroding my steep embankment?
Find all subarray with sum equal to number?
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)
Data science time! April 2019 and salary with experience
The Ask Question Wizard is Live!Validate decimal numbers in JavaScript - IsNumeric()How can I format numbers as dollars currency string in JavaScript?Convert JavaScript String to be all lower case?Which equals operator (== vs ===) should be used in JavaScript comparisons?How to replace all occurrences of a string in JavaScriptHow to find the sum of an array of numbersGenerating random whole numbers in JavaScript in a specific range?How to print a number with commas as thousands separators in JavaScriptGenerate random number between two numbers in JavaScript
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
Could you please tell me how to find all subarray with sum equal to number
Example
arr[] = [2, 4, 45, 6, 0, 19]
x = 51
Output: [2,4,45]
Or
arr[] = [1, 11, 100, 1, 0, 200, 3, 2, 1, 280]
x = 280
Output: [280]
I tried like that but not getting correct output
function getSubArray(arr, num)
var sum = 0,
blank = [];
var bigArr = []
for (var i = 0; i < arr.length; i++)
sum = arr[i];
if (blank.length === 0)
blank.push(arr[i]);
for (var j = 1; i < arr.length; j++)
sum += arr[j];
if (sum < num)
blank.push(arr[j])
else if (sum > num)
sum = 0;
blank = [];
break;
else
blank.push(arr[j])
bigArr.push(blank);
sum = 0;
blank = [];
return bigArr
console.log(getSubArray([1, 3, 6, 11, 1, 5, 4], 4));
for this expected output is
console.log(getSubArray([1, 3, 6, 11, 1, 5,4],4));
output: [1,3]
[4]
expected output
[[1,3], [4]] is my expected output
javascript
|
show 14 more comments
Could you please tell me how to find all subarray with sum equal to number
Example
arr[] = [2, 4, 45, 6, 0, 19]
x = 51
Output: [2,4,45]
Or
arr[] = [1, 11, 100, 1, 0, 200, 3, 2, 1, 280]
x = 280
Output: [280]
I tried like that but not getting correct output
function getSubArray(arr, num)
var sum = 0,
blank = [];
var bigArr = []
for (var i = 0; i < arr.length; i++)
sum = arr[i];
if (blank.length === 0)
blank.push(arr[i]);
for (var j = 1; i < arr.length; j++)
sum += arr[j];
if (sum < num)
blank.push(arr[j])
else if (sum > num)
sum = 0;
blank = [];
break;
else
blank.push(arr[j])
bigArr.push(blank);
sum = 0;
blank = [];
return bigArr
console.log(getSubArray([1, 3, 6, 11, 1, 5, 4], 4));
for this expected output is
console.log(getSubArray([1, 3, 6, 11, 1, 5,4],4));
output: [1,3]
[4]
expected output
[[1,3], [4]] is my expected output
javascript
2
Not able to make out anything from the question
– brk
Mar 22 at 9:18
@brk as mentioned I am not getting subarray using my function
– user944513
Mar 22 at 9:20
@brk given an array of numbers and a target number, find the smallest possible section of the array that when summed equals the target number. I think, I don't know if it's supposed to be a subarray (so, preserving order of the elements) or any valid combination of the array elements.
– VLAZ
Mar 22 at 9:20
@user944513 What happens when the numbers cannot add up to that number
– nick zoum
Mar 22 at 9:22
5
Do you mean sub-array or sub-sequence? Because sub-array is contiguous, but sub-sequence isn't
– bird
Mar 22 at 9:28
|
show 14 more comments
Could you please tell me how to find all subarray with sum equal to number
Example
arr[] = [2, 4, 45, 6, 0, 19]
x = 51
Output: [2,4,45]
Or
arr[] = [1, 11, 100, 1, 0, 200, 3, 2, 1, 280]
x = 280
Output: [280]
I tried like that but not getting correct output
function getSubArray(arr, num)
var sum = 0,
blank = [];
var bigArr = []
for (var i = 0; i < arr.length; i++)
sum = arr[i];
if (blank.length === 0)
blank.push(arr[i]);
for (var j = 1; i < arr.length; j++)
sum += arr[j];
if (sum < num)
blank.push(arr[j])
else if (sum > num)
sum = 0;
blank = [];
break;
else
blank.push(arr[j])
bigArr.push(blank);
sum = 0;
blank = [];
return bigArr
console.log(getSubArray([1, 3, 6, 11, 1, 5, 4], 4));
for this expected output is
console.log(getSubArray([1, 3, 6, 11, 1, 5,4],4));
output: [1,3]
[4]
expected output
[[1,3], [4]] is my expected output
javascript
Could you please tell me how to find all subarray with sum equal to number
Example
arr[] = [2, 4, 45, 6, 0, 19]
x = 51
Output: [2,4,45]
Or
arr[] = [1, 11, 100, 1, 0, 200, 3, 2, 1, 280]
x = 280
Output: [280]
I tried like that but not getting correct output
function getSubArray(arr, num)
var sum = 0,
blank = [];
var bigArr = []
for (var i = 0; i < arr.length; i++)
sum = arr[i];
if (blank.length === 0)
blank.push(arr[i]);
for (var j = 1; i < arr.length; j++)
sum += arr[j];
if (sum < num)
blank.push(arr[j])
else if (sum > num)
sum = 0;
blank = [];
break;
else
blank.push(arr[j])
bigArr.push(blank);
sum = 0;
blank = [];
return bigArr
console.log(getSubArray([1, 3, 6, 11, 1, 5, 4], 4));
for this expected output is
console.log(getSubArray([1, 3, 6, 11, 1, 5,4],4));
output: [1,3]
[4]
expected output
[[1,3], [4]] is my expected output
function getSubArray(arr, num)
var sum = 0,
blank = [];
var bigArr = []
for (var i = 0; i < arr.length; i++)
sum = arr[i];
if (blank.length === 0)
blank.push(arr[i]);
for (var j = 1; i < arr.length; j++)
sum += arr[j];
if (sum < num)
blank.push(arr[j])
else if (sum > num)
sum = 0;
blank = [];
break;
else
blank.push(arr[j])
bigArr.push(blank);
sum = 0;
blank = [];
return bigArr
console.log(getSubArray([1, 3, 6, 11, 1, 5, 4], 4));
function getSubArray(arr, num)
var sum = 0,
blank = [];
var bigArr = []
for (var i = 0; i < arr.length; i++)
sum = arr[i];
if (blank.length === 0)
blank.push(arr[i]);
for (var j = 1; i < arr.length; j++)
sum += arr[j];
if (sum < num)
blank.push(arr[j])
else if (sum > num)
sum = 0;
blank = [];
break;
else
blank.push(arr[j])
bigArr.push(blank);
sum = 0;
blank = [];
return bigArr
console.log(getSubArray([1, 3, 6, 11, 1, 5, 4], 4));
javascript
javascript
edited Mar 22 at 9:38
user944513
asked Mar 22 at 9:16
user944513user944513
3,4831463128
3,4831463128
2
Not able to make out anything from the question
– brk
Mar 22 at 9:18
@brk as mentioned I am not getting subarray using my function
– user944513
Mar 22 at 9:20
@brk given an array of numbers and a target number, find the smallest possible section of the array that when summed equals the target number. I think, I don't know if it's supposed to be a subarray (so, preserving order of the elements) or any valid combination of the array elements.
– VLAZ
Mar 22 at 9:20
@user944513 What happens when the numbers cannot add up to that number
– nick zoum
Mar 22 at 9:22
5
Do you mean sub-array or sub-sequence? Because sub-array is contiguous, but sub-sequence isn't
– bird
Mar 22 at 9:28
|
show 14 more comments
2
Not able to make out anything from the question
– brk
Mar 22 at 9:18
@brk as mentioned I am not getting subarray using my function
– user944513
Mar 22 at 9:20
@brk given an array of numbers and a target number, find the smallest possible section of the array that when summed equals the target number. I think, I don't know if it's supposed to be a subarray (so, preserving order of the elements) or any valid combination of the array elements.
– VLAZ
Mar 22 at 9:20
@user944513 What happens when the numbers cannot add up to that number
– nick zoum
Mar 22 at 9:22
5
Do you mean sub-array or sub-sequence? Because sub-array is contiguous, but sub-sequence isn't
– bird
Mar 22 at 9:28
2
2
Not able to make out anything from the question
– brk
Mar 22 at 9:18
Not able to make out anything from the question
– brk
Mar 22 at 9:18
@brk as mentioned I am not getting subarray using my function
– user944513
Mar 22 at 9:20
@brk as mentioned I am not getting subarray using my function
– user944513
Mar 22 at 9:20
@brk given an array of numbers and a target number, find the smallest possible section of the array that when summed equals the target number. I think, I don't know if it's supposed to be a subarray (so, preserving order of the elements) or any valid combination of the array elements.
– VLAZ
Mar 22 at 9:20
@brk given an array of numbers and a target number, find the smallest possible section of the array that when summed equals the target number. I think, I don't know if it's supposed to be a subarray (so, preserving order of the elements) or any valid combination of the array elements.
– VLAZ
Mar 22 at 9:20
@user944513 What happens when the numbers cannot add up to that number
– nick zoum
Mar 22 at 9:22
@user944513 What happens when the numbers cannot add up to that number
– nick zoum
Mar 22 at 9:22
5
5
Do you mean sub-array or sub-sequence? Because sub-array is contiguous, but sub-sequence isn't
– bird
Mar 22 at 9:28
Do you mean sub-array or sub-sequence? Because sub-array is contiguous, but sub-sequence isn't
– bird
Mar 22 at 9:28
|
show 14 more comments
8 Answers
8
active
oldest
votes
You could iterate the array and take either the next element or if no element is taken before omit this element.
function getSubset(array, sum)
function iter(temp, delta, index)
if (!delta) result.push(temp);
if (index >= array.length) return;
iter(temp.concat(array[index]), delta - array[index], index + 1);
if (!temp.length) iter(temp, delta, index + 1);
var result = [];
iter([], sum, 0);
return result;
console.log(getSubset([2, 4, 45, 6, 0, 19], 51)); // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4)); // [1, 3], [4]
If you tryconsole.log(getSubset([2, 4, 50, 45, 5,1, 0, 19,1], 51));
you get[45,5,1]
, instead of[50, 1]
– Vladimir Bogomolov
Mar 22 at 9:49
just as an improvement you could first filter the array and remove any numbers above our target sum.
– iacobalin
Mar 22 at 9:50
@VladimirBogomolov, ithink the returned elements should have a continuous index ...maybe not?
– Nina Scholz
Mar 22 at 9:51
@iacobalin, this approach does not work with negative values, because you need greater numbers as the target sum.
– Nina Scholz
Mar 22 at 9:52
1
@NinaScholz You may be right on this one as the guy asked about sub-arrays while I thought about sub-sets
– Marcus
Mar 22 at 10:41
|
show 6 more comments
This might not be exactly what's needed - might require tweaking as the logic may be flawed here.
I have commented the code for clarification.
var arr = [1, 3, 6, 11, 1, 5,4]; // Define array
var target = 31; // Define target
// filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
if(arr.reduce((a,b) => a + b) < target) // Check if we have enough numbers to make up that number
throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
// grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];
var toFind = target - getSum(); // get remainder to find
for(var i = withinRange.length - 1; i > -1; i--) // iterate from the top
if(toFind == withinRange[i]) // check if number is exactly what we need
numbers.push(withinRange[i]);
break;
else if(withinRange[i] <= toFind) // if number is smaller than what we look for
numbers.push(withinRange[i]);
toFind -= withinRange[i];
function getSum() // sum up our found numbers
if(numbers.length == 0) return 0;
return numbers.reduce((a,b) => a + b);
console.log([numbers, [target]]); // print numbers as desired output
console.log(target, getSum()) // print the target and our numbers
2
Very clear and well working solution.Might be a bit slow because of all the operations.
– Vladimir Bogomolov
Mar 22 at 9:55
1
@VladimirBogomolov Indeed, it might be slow, but it can be optimised. Things such as reduce can be called once for example.
– Adriani6
Mar 22 at 9:58
add a comment |
It will give all the available case. And I use the test case of @Nina Scholz
const sum = arr => arr.reduce((a,b) => a + b)
function cal(arr, x)
const rs = []
for (let i = 0; i< arr.length; i++)
const tmp = []
for (let j=i; j<arr.length; j++ )
tmp.push(arr[j])
if(sum(tmp) === x) rs.push([...tmp])
return rs
console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]
what about[2,4,45,0]
?
– nick zoum
Mar 22 at 10:28
@nickzoum It isn't contiguous, is it?
– bird
Mar 22 at 10:34
sorry, i completely missed that part
– nick zoum
Mar 22 at 10:48
add a comment |
This will try every possible permutation of the array (will stop further permutations once limit is reached)
function test(arr, num) "Not found";
function helper(start, total, list)
var result = [];
// Using for loop is faster because you can start from desired index without using filter, slice, splice ...
for (var index = start; index < arr.length; index++)
var item = arr[index];
// If the total is too large the path can be skipped alltogether
if (total + item <= num)
// Check lists if number was not included
var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
total += item;
result.push(item);
//if (total === num) index = arr.length; add for efficiency
if (total === num) allLists.push(list.concat(result));
console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]
If you want to make it more efficient and just return one of the resulted array just comment out the recursive call. You can also un-comment the line that exits the loop once the limit has been reached (will skip 0s).
Uncaught ReferenceError: getMin is not defined
– Marcus
Mar 22 at 9:56
@Marcus Sorry i renamed it tohelper
and didnt change all the references
– nick zoum
Mar 22 at 9:57
@Marcus this solution will return every possible subarray
– nick zoum
Mar 22 at 10:29
add a comment |
If the question is about finding all subsets (rather than subarrays) with the given cross sum it is also known as the perfect sum problem.
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
function printSubsetsRec(arr, i, sum, p)
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sun OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0][sum])
p.push(arr[i]);
console.log(p);
return;
// If sum becomes 0
if (i == 0 && sum == 0)
console.log(p);
return;
// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum])
// Create a new vector to store path
var b = p.slice(0);
printSubsetsRec(arr, i-1, sum, b);
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
p.push(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
// Prints all subsets of arr[0..n-1] with sum 0.
function printAllSubsets(arr, sum)
printAllSubsets([1,2,3,4,5], 10);
add a comment |
Solution
'use strict';
function print(arr[], i, j)
let k = 0;
for (k = i; k <= j; k += 1)
console.log(arr[k]);
function findSubArrays(arr[], sum)
let n = arr.length;
let i;
let j;
let sum_so_far;
for (i = 0; i<n; i+= 1)
sum_so_far = 0;
for (j = i; j < n; j++)
sum_so_far += arr[j];
if (sum_so_far === sum)
print(arr, i, j);
add a comment |
I would first loop depending on the size of expected arrays.
After that loop for looking for first part of the array which should be filled with positions that will match the desired number.
For example for x= 4 having arr=[5,4,32,8,2,1,2,2,3,4,4]
It would first take the 4's. Output will start on [ [4], [4], [4], ..... ] for positions 1,9,10 (respectively)
Then go for the arrays resulting sum of 2 elements [ ... [2,2], [2,2],[2,2], [1,3] ...] ( positions 4+6, position 4+7 position6+7 and position 5+8)
You would probably want to use another function to sum and check at this point.
Now will do the same for sum of 3 elements (if any) and so on, having max loop set at number of original array (the resulting number could be the sum of all the elements in the array).
The resulting example would be [ [4], [4], [4], [2,2], [2,2],[2,2], [1,3]]
add a comment |
function combinations(array)
return new Array(1 << array.length).fill().map(
(e1,i) => array.filter((e2, j) => i & 1 << j));
function add(acc,a)
return acc + a
combinations([2, 4, 45, 6, 0, 19]).filter( subarray => subarray.reduce(add, 0) == 51 )
output
[[2,4,45],[45,6],[2,4,45,0],[45,6,0]]
combinations([1, 11, 100, 1, 0, 200, 3, 2, 1, 280]).filter( subarray => subarray.reduce(add, 0) == 280 )
output
[[280],[0,280]]
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%2f55296323%2ffind-all-subarray-with-sum-equal-to-number%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
8 Answers
8
active
oldest
votes
8 Answers
8
active
oldest
votes
active
oldest
votes
active
oldest
votes
You could iterate the array and take either the next element or if no element is taken before omit this element.
function getSubset(array, sum)
function iter(temp, delta, index)
if (!delta) result.push(temp);
if (index >= array.length) return;
iter(temp.concat(array[index]), delta - array[index], index + 1);
if (!temp.length) iter(temp, delta, index + 1);
var result = [];
iter([], sum, 0);
return result;
console.log(getSubset([2, 4, 45, 6, 0, 19], 51)); // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4)); // [1, 3], [4]
If you tryconsole.log(getSubset([2, 4, 50, 45, 5,1, 0, 19,1], 51));
you get[45,5,1]
, instead of[50, 1]
– Vladimir Bogomolov
Mar 22 at 9:49
just as an improvement you could first filter the array and remove any numbers above our target sum.
– iacobalin
Mar 22 at 9:50
@VladimirBogomolov, ithink the returned elements should have a continuous index ...maybe not?
– Nina Scholz
Mar 22 at 9:51
@iacobalin, this approach does not work with negative values, because you need greater numbers as the target sum.
– Nina Scholz
Mar 22 at 9:52
1
@NinaScholz You may be right on this one as the guy asked about sub-arrays while I thought about sub-sets
– Marcus
Mar 22 at 10:41
|
show 6 more comments
You could iterate the array and take either the next element or if no element is taken before omit this element.
function getSubset(array, sum)
function iter(temp, delta, index)
if (!delta) result.push(temp);
if (index >= array.length) return;
iter(temp.concat(array[index]), delta - array[index], index + 1);
if (!temp.length) iter(temp, delta, index + 1);
var result = [];
iter([], sum, 0);
return result;
console.log(getSubset([2, 4, 45, 6, 0, 19], 51)); // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4)); // [1, 3], [4]
If you tryconsole.log(getSubset([2, 4, 50, 45, 5,1, 0, 19,1], 51));
you get[45,5,1]
, instead of[50, 1]
– Vladimir Bogomolov
Mar 22 at 9:49
just as an improvement you could first filter the array and remove any numbers above our target sum.
– iacobalin
Mar 22 at 9:50
@VladimirBogomolov, ithink the returned elements should have a continuous index ...maybe not?
– Nina Scholz
Mar 22 at 9:51
@iacobalin, this approach does not work with negative values, because you need greater numbers as the target sum.
– Nina Scholz
Mar 22 at 9:52
1
@NinaScholz You may be right on this one as the guy asked about sub-arrays while I thought about sub-sets
– Marcus
Mar 22 at 10:41
|
show 6 more comments
You could iterate the array and take either the next element or if no element is taken before omit this element.
function getSubset(array, sum)
function iter(temp, delta, index)
if (!delta) result.push(temp);
if (index >= array.length) return;
iter(temp.concat(array[index]), delta - array[index], index + 1);
if (!temp.length) iter(temp, delta, index + 1);
var result = [];
iter([], sum, 0);
return result;
console.log(getSubset([2, 4, 45, 6, 0, 19], 51)); // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4)); // [1, 3], [4]
You could iterate the array and take either the next element or if no element is taken before omit this element.
function getSubset(array, sum)
function iter(temp, delta, index)
if (!delta) result.push(temp);
if (index >= array.length) return;
iter(temp.concat(array[index]), delta - array[index], index + 1);
if (!temp.length) iter(temp, delta, index + 1);
var result = [];
iter([], sum, 0);
return result;
console.log(getSubset([2, 4, 45, 6, 0, 19], 51)); // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4)); // [1, 3], [4]
function getSubset(array, sum)
function iter(temp, delta, index)
if (!delta) result.push(temp);
if (index >= array.length) return;
iter(temp.concat(array[index]), delta - array[index], index + 1);
if (!temp.length) iter(temp, delta, index + 1);
var result = [];
iter([], sum, 0);
return result;
console.log(getSubset([2, 4, 45, 6, 0, 19], 51)); // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4)); // [1, 3], [4]
function getSubset(array, sum)
function iter(temp, delta, index)
if (!delta) result.push(temp);
if (index >= array.length) return;
iter(temp.concat(array[index]), delta - array[index], index + 1);
if (!temp.length) iter(temp, delta, index + 1);
var result = [];
iter([], sum, 0);
return result;
console.log(getSubset([2, 4, 45, 6, 0, 19], 51)); // [2, 4, 45], [45, 6], [45, 6, 0]
console.log(getSubset([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280]
console.log(getSubset([1, 3, 6, 11, 1, 5, 4], 4)); // [1, 3], [4]
edited Mar 22 at 10:10
answered Mar 22 at 9:45
Nina ScholzNina Scholz
199k15112182
199k15112182
If you tryconsole.log(getSubset([2, 4, 50, 45, 5,1, 0, 19,1], 51));
you get[45,5,1]
, instead of[50, 1]
– Vladimir Bogomolov
Mar 22 at 9:49
just as an improvement you could first filter the array and remove any numbers above our target sum.
– iacobalin
Mar 22 at 9:50
@VladimirBogomolov, ithink the returned elements should have a continuous index ...maybe not?
– Nina Scholz
Mar 22 at 9:51
@iacobalin, this approach does not work with negative values, because you need greater numbers as the target sum.
– Nina Scholz
Mar 22 at 9:52
1
@NinaScholz You may be right on this one as the guy asked about sub-arrays while I thought about sub-sets
– Marcus
Mar 22 at 10:41
|
show 6 more comments
If you tryconsole.log(getSubset([2, 4, 50, 45, 5,1, 0, 19,1], 51));
you get[45,5,1]
, instead of[50, 1]
– Vladimir Bogomolov
Mar 22 at 9:49
just as an improvement you could first filter the array and remove any numbers above our target sum.
– iacobalin
Mar 22 at 9:50
@VladimirBogomolov, ithink the returned elements should have a continuous index ...maybe not?
– Nina Scholz
Mar 22 at 9:51
@iacobalin, this approach does not work with negative values, because you need greater numbers as the target sum.
– Nina Scholz
Mar 22 at 9:52
1
@NinaScholz You may be right on this one as the guy asked about sub-arrays while I thought about sub-sets
– Marcus
Mar 22 at 10:41
If you try
console.log(getSubset([2, 4, 50, 45, 5,1, 0, 19,1], 51));
you get [45,5,1]
, instead of [50, 1]
– Vladimir Bogomolov
Mar 22 at 9:49
If you try
console.log(getSubset([2, 4, 50, 45, 5,1, 0, 19,1], 51));
you get [45,5,1]
, instead of [50, 1]
– Vladimir Bogomolov
Mar 22 at 9:49
just as an improvement you could first filter the array and remove any numbers above our target sum.
– iacobalin
Mar 22 at 9:50
just as an improvement you could first filter the array and remove any numbers above our target sum.
– iacobalin
Mar 22 at 9:50
@VladimirBogomolov, ithink the returned elements should have a continuous index ...maybe not?
– Nina Scholz
Mar 22 at 9:51
@VladimirBogomolov, ithink the returned elements should have a continuous index ...maybe not?
– Nina Scholz
Mar 22 at 9:51
@iacobalin, this approach does not work with negative values, because you need greater numbers as the target sum.
– Nina Scholz
Mar 22 at 9:52
@iacobalin, this approach does not work with negative values, because you need greater numbers as the target sum.
– Nina Scholz
Mar 22 at 9:52
1
1
@NinaScholz You may be right on this one as the guy asked about sub-arrays while I thought about sub-sets
– Marcus
Mar 22 at 10:41
@NinaScholz You may be right on this one as the guy asked about sub-arrays while I thought about sub-sets
– Marcus
Mar 22 at 10:41
|
show 6 more comments
This might not be exactly what's needed - might require tweaking as the logic may be flawed here.
I have commented the code for clarification.
var arr = [1, 3, 6, 11, 1, 5,4]; // Define array
var target = 31; // Define target
// filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
if(arr.reduce((a,b) => a + b) < target) // Check if we have enough numbers to make up that number
throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
// grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];
var toFind = target - getSum(); // get remainder to find
for(var i = withinRange.length - 1; i > -1; i--) // iterate from the top
if(toFind == withinRange[i]) // check if number is exactly what we need
numbers.push(withinRange[i]);
break;
else if(withinRange[i] <= toFind) // if number is smaller than what we look for
numbers.push(withinRange[i]);
toFind -= withinRange[i];
function getSum() // sum up our found numbers
if(numbers.length == 0) return 0;
return numbers.reduce((a,b) => a + b);
console.log([numbers, [target]]); // print numbers as desired output
console.log(target, getSum()) // print the target and our numbers
2
Very clear and well working solution.Might be a bit slow because of all the operations.
– Vladimir Bogomolov
Mar 22 at 9:55
1
@VladimirBogomolov Indeed, it might be slow, but it can be optimised. Things such as reduce can be called once for example.
– Adriani6
Mar 22 at 9:58
add a comment |
This might not be exactly what's needed - might require tweaking as the logic may be flawed here.
I have commented the code for clarification.
var arr = [1, 3, 6, 11, 1, 5,4]; // Define array
var target = 31; // Define target
// filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
if(arr.reduce((a,b) => a + b) < target) // Check if we have enough numbers to make up that number
throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
// grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];
var toFind = target - getSum(); // get remainder to find
for(var i = withinRange.length - 1; i > -1; i--) // iterate from the top
if(toFind == withinRange[i]) // check if number is exactly what we need
numbers.push(withinRange[i]);
break;
else if(withinRange[i] <= toFind) // if number is smaller than what we look for
numbers.push(withinRange[i]);
toFind -= withinRange[i];
function getSum() // sum up our found numbers
if(numbers.length == 0) return 0;
return numbers.reduce((a,b) => a + b);
console.log([numbers, [target]]); // print numbers as desired output
console.log(target, getSum()) // print the target and our numbers
2
Very clear and well working solution.Might be a bit slow because of all the operations.
– Vladimir Bogomolov
Mar 22 at 9:55
1
@VladimirBogomolov Indeed, it might be slow, but it can be optimised. Things such as reduce can be called once for example.
– Adriani6
Mar 22 at 9:58
add a comment |
This might not be exactly what's needed - might require tweaking as the logic may be flawed here.
I have commented the code for clarification.
var arr = [1, 3, 6, 11, 1, 5,4]; // Define array
var target = 31; // Define target
// filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
if(arr.reduce((a,b) => a + b) < target) // Check if we have enough numbers to make up that number
throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
// grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];
var toFind = target - getSum(); // get remainder to find
for(var i = withinRange.length - 1; i > -1; i--) // iterate from the top
if(toFind == withinRange[i]) // check if number is exactly what we need
numbers.push(withinRange[i]);
break;
else if(withinRange[i] <= toFind) // if number is smaller than what we look for
numbers.push(withinRange[i]);
toFind -= withinRange[i];
function getSum() // sum up our found numbers
if(numbers.length == 0) return 0;
return numbers.reduce((a,b) => a + b);
console.log([numbers, [target]]); // print numbers as desired output
console.log(target, getSum()) // print the target and our numbers
This might not be exactly what's needed - might require tweaking as the logic may be flawed here.
I have commented the code for clarification.
var arr = [1, 3, 6, 11, 1, 5,4]; // Define array
var target = 31; // Define target
// filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
if(arr.reduce((a,b) => a + b) < target) // Check if we have enough numbers to make up that number
throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
// grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];
var toFind = target - getSum(); // get remainder to find
for(var i = withinRange.length - 1; i > -1; i--) // iterate from the top
if(toFind == withinRange[i]) // check if number is exactly what we need
numbers.push(withinRange[i]);
break;
else if(withinRange[i] <= toFind) // if number is smaller than what we look for
numbers.push(withinRange[i]);
toFind -= withinRange[i];
function getSum() // sum up our found numbers
if(numbers.length == 0) return 0;
return numbers.reduce((a,b) => a + b);
console.log([numbers, [target]]); // print numbers as desired output
console.log(target, getSum()) // print the target and our numbers
var arr = [1, 3, 6, 11, 1, 5,4]; // Define array
var target = 31; // Define target
// filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
if(arr.reduce((a,b) => a + b) < target) // Check if we have enough numbers to make up that number
throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
// grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];
var toFind = target - getSum(); // get remainder to find
for(var i = withinRange.length - 1; i > -1; i--) // iterate from the top
if(toFind == withinRange[i]) // check if number is exactly what we need
numbers.push(withinRange[i]);
break;
else if(withinRange[i] <= toFind) // if number is smaller than what we look for
numbers.push(withinRange[i]);
toFind -= withinRange[i];
function getSum() // sum up our found numbers
if(numbers.length == 0) return 0;
return numbers.reduce((a,b) => a + b);
console.log([numbers, [target]]); // print numbers as desired output
console.log(target, getSum()) // print the target and our numbers
var arr = [1, 3, 6, 11, 1, 5,4]; // Define array
var target = 31; // Define target
// filter the numbers higher than target and sort rest ascending
var withinRange = arr.filter(x => x <= target).sort((a, b) => a - b);
if(arr.reduce((a,b) => a + b) < target) // Check if we have enough numbers to make up that number
throw "The max you can get out of your selection is: " + arr.reduce((a,b) => a + b);
// grab the highest number as a starting point and remove it from our array of numbers
var numbers = [withinRange.pop()];
var toFind = target - getSum(); // get remainder to find
for(var i = withinRange.length - 1; i > -1; i--) // iterate from the top
if(toFind == withinRange[i]) // check if number is exactly what we need
numbers.push(withinRange[i]);
break;
else if(withinRange[i] <= toFind) // if number is smaller than what we look for
numbers.push(withinRange[i]);
toFind -= withinRange[i];
function getSum() // sum up our found numbers
if(numbers.length == 0) return 0;
return numbers.reduce((a,b) => a + b);
console.log([numbers, [target]]); // print numbers as desired output
console.log(target, getSum()) // print the target and our numbers
edited Mar 22 at 10:20
answered Mar 22 at 9:51
Adriani6Adriani6
5,19121531
5,19121531
2
Very clear and well working solution.Might be a bit slow because of all the operations.
– Vladimir Bogomolov
Mar 22 at 9:55
1
@VladimirBogomolov Indeed, it might be slow, but it can be optimised. Things such as reduce can be called once for example.
– Adriani6
Mar 22 at 9:58
add a comment |
2
Very clear and well working solution.Might be a bit slow because of all the operations.
– Vladimir Bogomolov
Mar 22 at 9:55
1
@VladimirBogomolov Indeed, it might be slow, but it can be optimised. Things such as reduce can be called once for example.
– Adriani6
Mar 22 at 9:58
2
2
Very clear and well working solution.Might be a bit slow because of all the operations.
– Vladimir Bogomolov
Mar 22 at 9:55
Very clear and well working solution.Might be a bit slow because of all the operations.
– Vladimir Bogomolov
Mar 22 at 9:55
1
1
@VladimirBogomolov Indeed, it might be slow, but it can be optimised. Things such as reduce can be called once for example.
– Adriani6
Mar 22 at 9:58
@VladimirBogomolov Indeed, it might be slow, but it can be optimised. Things such as reduce can be called once for example.
– Adriani6
Mar 22 at 9:58
add a comment |
It will give all the available case. And I use the test case of @Nina Scholz
const sum = arr => arr.reduce((a,b) => a + b)
function cal(arr, x)
const rs = []
for (let i = 0; i< arr.length; i++)
const tmp = []
for (let j=i; j<arr.length; j++ )
tmp.push(arr[j])
if(sum(tmp) === x) rs.push([...tmp])
return rs
console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]
what about[2,4,45,0]
?
– nick zoum
Mar 22 at 10:28
@nickzoum It isn't contiguous, is it?
– bird
Mar 22 at 10:34
sorry, i completely missed that part
– nick zoum
Mar 22 at 10:48
add a comment |
It will give all the available case. And I use the test case of @Nina Scholz
const sum = arr => arr.reduce((a,b) => a + b)
function cal(arr, x)
const rs = []
for (let i = 0; i< arr.length; i++)
const tmp = []
for (let j=i; j<arr.length; j++ )
tmp.push(arr[j])
if(sum(tmp) === x) rs.push([...tmp])
return rs
console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]
what about[2,4,45,0]
?
– nick zoum
Mar 22 at 10:28
@nickzoum It isn't contiguous, is it?
– bird
Mar 22 at 10:34
sorry, i completely missed that part
– nick zoum
Mar 22 at 10:48
add a comment |
It will give all the available case. And I use the test case of @Nina Scholz
const sum = arr => arr.reduce((a,b) => a + b)
function cal(arr, x)
const rs = []
for (let i = 0; i< arr.length; i++)
const tmp = []
for (let j=i; j<arr.length; j++ )
tmp.push(arr[j])
if(sum(tmp) === x) rs.push([...tmp])
return rs
console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]
It will give all the available case. And I use the test case of @Nina Scholz
const sum = arr => arr.reduce((a,b) => a + b)
function cal(arr, x)
const rs = []
for (let i = 0; i< arr.length; i++)
const tmp = []
for (let j=i; j<arr.length; j++ )
tmp.push(arr[j])
if(sum(tmp) === x) rs.push([...tmp])
return rs
console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]
const sum = arr => arr.reduce((a,b) => a + b)
function cal(arr, x)
const rs = []
for (let i = 0; i< arr.length; i++)
const tmp = []
for (let j=i; j<arr.length; j++ )
tmp.push(arr[j])
if(sum(tmp) === x) rs.push([...tmp])
return rs
console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]
const sum = arr => arr.reduce((a,b) => a + b)
function cal(arr, x)
const rs = []
for (let i = 0; i< arr.length; i++)
const tmp = []
for (let j=i; j<arr.length; j++ )
tmp.push(arr[j])
if(sum(tmp) === x) rs.push([...tmp])
return rs
console.log(cal([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)) // -> [280]
console.log(cal([2, 4, 45, 6, 0, 19], 51)); // -> [2, 4, 45] [45, 6] [45, 6, 0]
console.log(cal([1, 3, 6, 11, 1, 5, 4], 4)); // -> [1,3] [4]
answered Mar 22 at 9:58
birdbird
1,136820
1,136820
what about[2,4,45,0]
?
– nick zoum
Mar 22 at 10:28
@nickzoum It isn't contiguous, is it?
– bird
Mar 22 at 10:34
sorry, i completely missed that part
– nick zoum
Mar 22 at 10:48
add a comment |
what about[2,4,45,0]
?
– nick zoum
Mar 22 at 10:28
@nickzoum It isn't contiguous, is it?
– bird
Mar 22 at 10:34
sorry, i completely missed that part
– nick zoum
Mar 22 at 10:48
what about
[2,4,45,0]
?– nick zoum
Mar 22 at 10:28
what about
[2,4,45,0]
?– nick zoum
Mar 22 at 10:28
@nickzoum It isn't contiguous, is it?
– bird
Mar 22 at 10:34
@nickzoum It isn't contiguous, is it?
– bird
Mar 22 at 10:34
sorry, i completely missed that part
– nick zoum
Mar 22 at 10:48
sorry, i completely missed that part
– nick zoum
Mar 22 at 10:48
add a comment |
This will try every possible permutation of the array (will stop further permutations once limit is reached)
function test(arr, num) "Not found";
function helper(start, total, list)
var result = [];
// Using for loop is faster because you can start from desired index without using filter, slice, splice ...
for (var index = start; index < arr.length; index++)
var item = arr[index];
// If the total is too large the path can be skipped alltogether
if (total + item <= num)
// Check lists if number was not included
var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
total += item;
result.push(item);
//if (total === num) index = arr.length; add for efficiency
if (total === num) allLists.push(list.concat(result));
console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]
If you want to make it more efficient and just return one of the resulted array just comment out the recursive call. You can also un-comment the line that exits the loop once the limit has been reached (will skip 0s).
Uncaught ReferenceError: getMin is not defined
– Marcus
Mar 22 at 9:56
@Marcus Sorry i renamed it tohelper
and didnt change all the references
– nick zoum
Mar 22 at 9:57
@Marcus this solution will return every possible subarray
– nick zoum
Mar 22 at 10:29
add a comment |
This will try every possible permutation of the array (will stop further permutations once limit is reached)
function test(arr, num) "Not found";
function helper(start, total, list)
var result = [];
// Using for loop is faster because you can start from desired index without using filter, slice, splice ...
for (var index = start; index < arr.length; index++)
var item = arr[index];
// If the total is too large the path can be skipped alltogether
if (total + item <= num)
// Check lists if number was not included
var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
total += item;
result.push(item);
//if (total === num) index = arr.length; add for efficiency
if (total === num) allLists.push(list.concat(result));
console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]
If you want to make it more efficient and just return one of the resulted array just comment out the recursive call. You can also un-comment the line that exits the loop once the limit has been reached (will skip 0s).
Uncaught ReferenceError: getMin is not defined
– Marcus
Mar 22 at 9:56
@Marcus Sorry i renamed it tohelper
and didnt change all the references
– nick zoum
Mar 22 at 9:57
@Marcus this solution will return every possible subarray
– nick zoum
Mar 22 at 10:29
add a comment |
This will try every possible permutation of the array (will stop further permutations once limit is reached)
function test(arr, num) "Not found";
function helper(start, total, list)
var result = [];
// Using for loop is faster because you can start from desired index without using filter, slice, splice ...
for (var index = start; index < arr.length; index++)
var item = arr[index];
// If the total is too large the path can be skipped alltogether
if (total + item <= num)
// Check lists if number was not included
var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
total += item;
result.push(item);
//if (total === num) index = arr.length; add for efficiency
if (total === num) allLists.push(list.concat(result));
console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]
If you want to make it more efficient and just return one of the resulted array just comment out the recursive call. You can also un-comment the line that exits the loop once the limit has been reached (will skip 0s).
This will try every possible permutation of the array (will stop further permutations once limit is reached)
function test(arr, num) "Not found";
function helper(start, total, list)
var result = [];
// Using for loop is faster because you can start from desired index without using filter, slice, splice ...
for (var index = start; index < arr.length; index++)
var item = arr[index];
// If the total is too large the path can be skipped alltogether
if (total + item <= num)
// Check lists if number was not included
var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
total += item;
result.push(item);
//if (total === num) index = arr.length; add for efficiency
if (total === num) allLists.push(list.concat(result));
console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]
If you want to make it more efficient and just return one of the resulted array just comment out the recursive call. You can also un-comment the line that exits the loop once the limit has been reached (will skip 0s).
function test(arr, num) "Not found";
function helper(start, total, list)
var result = [];
// Using for loop is faster because you can start from desired index without using filter, slice, splice ...
for (var index = start; index < arr.length; index++)
var item = arr[index];
// If the total is too large the path can be skipped alltogether
if (total + item <= num)
// Check lists if number was not included
var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
total += item;
result.push(item);
//if (total === num) index = arr.length; add for efficiency
if (total === num) allLists.push(list.concat(result));
console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]
function test(arr, num) "Not found";
function helper(start, total, list)
var result = [];
// Using for loop is faster because you can start from desired index without using filter, slice, splice ...
for (var index = start; index < arr.length; index++)
var item = arr[index];
// If the total is too large the path can be skipped alltogether
if (total + item <= num)
// Check lists if number was not included
var test = helper(index + 1, total, list.concat(result)); // remove for efficiency
total += item;
result.push(item);
//if (total === num) index = arr.length; add for efficiency
if (total === num) allLists.push(list.concat(result));
console.log(test([2, 4, 45, 6, 0, 19], 51)); // [2,4,45] [2,4,45,0] [6,45] [6,45,0]
console.log(test([1, 11, 100, 1, 0, 200, 3, 2, 1, 280], 280)); // [280] [280,0]
edited Mar 22 at 10:33
answered Mar 22 at 9:53
nick zoumnick zoum
2,72411542
2,72411542
Uncaught ReferenceError: getMin is not defined
– Marcus
Mar 22 at 9:56
@Marcus Sorry i renamed it tohelper
and didnt change all the references
– nick zoum
Mar 22 at 9:57
@Marcus this solution will return every possible subarray
– nick zoum
Mar 22 at 10:29
add a comment |
Uncaught ReferenceError: getMin is not defined
– Marcus
Mar 22 at 9:56
@Marcus Sorry i renamed it tohelper
and didnt change all the references
– nick zoum
Mar 22 at 9:57
@Marcus this solution will return every possible subarray
– nick zoum
Mar 22 at 10:29
Uncaught ReferenceError: getMin is not defined
– Marcus
Mar 22 at 9:56
Uncaught ReferenceError: getMin is not defined
– Marcus
Mar 22 at 9:56
@Marcus Sorry i renamed it to
helper
and didnt change all the references– nick zoum
Mar 22 at 9:57
@Marcus Sorry i renamed it to
helper
and didnt change all the references– nick zoum
Mar 22 at 9:57
@Marcus this solution will return every possible subarray
– nick zoum
Mar 22 at 10:29
@Marcus this solution will return every possible subarray
– nick zoum
Mar 22 at 10:29
add a comment |
If the question is about finding all subsets (rather than subarrays) with the given cross sum it is also known as the perfect sum problem.
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
function printSubsetsRec(arr, i, sum, p)
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sun OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0][sum])
p.push(arr[i]);
console.log(p);
return;
// If sum becomes 0
if (i == 0 && sum == 0)
console.log(p);
return;
// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum])
// Create a new vector to store path
var b = p.slice(0);
printSubsetsRec(arr, i-1, sum, b);
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
p.push(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
// Prints all subsets of arr[0..n-1] with sum 0.
function printAllSubsets(arr, sum)
printAllSubsets([1,2,3,4,5], 10);
add a comment |
If the question is about finding all subsets (rather than subarrays) with the given cross sum it is also known as the perfect sum problem.
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
function printSubsetsRec(arr, i, sum, p)
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sun OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0][sum])
p.push(arr[i]);
console.log(p);
return;
// If sum becomes 0
if (i == 0 && sum == 0)
console.log(p);
return;
// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum])
// Create a new vector to store path
var b = p.slice(0);
printSubsetsRec(arr, i-1, sum, b);
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
p.push(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
// Prints all subsets of arr[0..n-1] with sum 0.
function printAllSubsets(arr, sum)
printAllSubsets([1,2,3,4,5], 10);
add a comment |
If the question is about finding all subsets (rather than subarrays) with the given cross sum it is also known as the perfect sum problem.
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
function printSubsetsRec(arr, i, sum, p)
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sun OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0][sum])
p.push(arr[i]);
console.log(p);
return;
// If sum becomes 0
if (i == 0 && sum == 0)
console.log(p);
return;
// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum])
// Create a new vector to store path
var b = p.slice(0);
printSubsetsRec(arr, i-1, sum, b);
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
p.push(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
// Prints all subsets of arr[0..n-1] with sum 0.
function printAllSubsets(arr, sum)
printAllSubsets([1,2,3,4,5], 10);
If the question is about finding all subsets (rather than subarrays) with the given cross sum it is also known as the perfect sum problem.
https://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/
// A recursive function to print all subsets with the
// help of dp[][]. Vector p[] stores current subset.
function printSubsetsRec(arr, i, sum, p)
// If we reached end and sum is non-zero. We print
// p[] only if arr[0] is equal to sun OR dp[0][sum]
// is true.
if (i == 0 && sum != 0 && dp[0][sum])
p.push(arr[i]);
console.log(p);
return;
// If sum becomes 0
if (i == 0 && sum == 0)
console.log(p);
return;
// If given sum can be achieved after ignoring
// current element.
if (dp[i-1][sum])
// Create a new vector to store path
var b = p.slice(0);
printSubsetsRec(arr, i-1, sum, b);
// If given sum can be achieved after considering
// current element.
if (sum >= arr[i] && dp[i-1][sum-arr[i]])
p.push(arr[i]);
printSubsetsRec(arr, i-1, sum-arr[i], p);
// Prints all subsets of arr[0..n-1] with sum 0.
function printAllSubsets(arr, sum)
printAllSubsets([1,2,3,4,5], 10);
edited Mar 22 at 14:46
answered Mar 22 at 10:03
MarcusMarcus
644517
644517
add a comment |
add a comment |
Solution
'use strict';
function print(arr[], i, j)
let k = 0;
for (k = i; k <= j; k += 1)
console.log(arr[k]);
function findSubArrays(arr[], sum)
let n = arr.length;
let i;
let j;
let sum_so_far;
for (i = 0; i<n; i+= 1)
sum_so_far = 0;
for (j = i; j < n; j++)
sum_so_far += arr[j];
if (sum_so_far === sum)
print(arr, i, j);
add a comment |
Solution
'use strict';
function print(arr[], i, j)
let k = 0;
for (k = i; k <= j; k += 1)
console.log(arr[k]);
function findSubArrays(arr[], sum)
let n = arr.length;
let i;
let j;
let sum_so_far;
for (i = 0; i<n; i+= 1)
sum_so_far = 0;
for (j = i; j < n; j++)
sum_so_far += arr[j];
if (sum_so_far === sum)
print(arr, i, j);
add a comment |
Solution
'use strict';
function print(arr[], i, j)
let k = 0;
for (k = i; k <= j; k += 1)
console.log(arr[k]);
function findSubArrays(arr[], sum)
let n = arr.length;
let i;
let j;
let sum_so_far;
for (i = 0; i<n; i+= 1)
sum_so_far = 0;
for (j = i; j < n; j++)
sum_so_far += arr[j];
if (sum_so_far === sum)
print(arr, i, j);
Solution
'use strict';
function print(arr[], i, j)
let k = 0;
for (k = i; k <= j; k += 1)
console.log(arr[k]);
function findSubArrays(arr[], sum)
let n = arr.length;
let i;
let j;
let sum_so_far;
for (i = 0; i<n; i+= 1)
sum_so_far = 0;
for (j = i; j < n; j++)
sum_so_far += arr[j];
if (sum_so_far === sum)
print(arr, i, j);
answered Mar 22 at 9:49
Naveen VigneshNaveen Vignesh
384213
384213
add a comment |
add a comment |
I would first loop depending on the size of expected arrays.
After that loop for looking for first part of the array which should be filled with positions that will match the desired number.
For example for x= 4 having arr=[5,4,32,8,2,1,2,2,3,4,4]
It would first take the 4's. Output will start on [ [4], [4], [4], ..... ] for positions 1,9,10 (respectively)
Then go for the arrays resulting sum of 2 elements [ ... [2,2], [2,2],[2,2], [1,3] ...] ( positions 4+6, position 4+7 position6+7 and position 5+8)
You would probably want to use another function to sum and check at this point.
Now will do the same for sum of 3 elements (if any) and so on, having max loop set at number of original array (the resulting number could be the sum of all the elements in the array).
The resulting example would be [ [4], [4], [4], [2,2], [2,2],[2,2], [1,3]]
add a comment |
I would first loop depending on the size of expected arrays.
After that loop for looking for first part of the array which should be filled with positions that will match the desired number.
For example for x= 4 having arr=[5,4,32,8,2,1,2,2,3,4,4]
It would first take the 4's. Output will start on [ [4], [4], [4], ..... ] for positions 1,9,10 (respectively)
Then go for the arrays resulting sum of 2 elements [ ... [2,2], [2,2],[2,2], [1,3] ...] ( positions 4+6, position 4+7 position6+7 and position 5+8)
You would probably want to use another function to sum and check at this point.
Now will do the same for sum of 3 elements (if any) and so on, having max loop set at number of original array (the resulting number could be the sum of all the elements in the array).
The resulting example would be [ [4], [4], [4], [2,2], [2,2],[2,2], [1,3]]
add a comment |
I would first loop depending on the size of expected arrays.
After that loop for looking for first part of the array which should be filled with positions that will match the desired number.
For example for x= 4 having arr=[5,4,32,8,2,1,2,2,3,4,4]
It would first take the 4's. Output will start on [ [4], [4], [4], ..... ] for positions 1,9,10 (respectively)
Then go for the arrays resulting sum of 2 elements [ ... [2,2], [2,2],[2,2], [1,3] ...] ( positions 4+6, position 4+7 position6+7 and position 5+8)
You would probably want to use another function to sum and check at this point.
Now will do the same for sum of 3 elements (if any) and so on, having max loop set at number of original array (the resulting number could be the sum of all the elements in the array).
The resulting example would be [ [4], [4], [4], [2,2], [2,2],[2,2], [1,3]]
I would first loop depending on the size of expected arrays.
After that loop for looking for first part of the array which should be filled with positions that will match the desired number.
For example for x= 4 having arr=[5,4,32,8,2,1,2,2,3,4,4]
It would first take the 4's. Output will start on [ [4], [4], [4], ..... ] for positions 1,9,10 (respectively)
Then go for the arrays resulting sum of 2 elements [ ... [2,2], [2,2],[2,2], [1,3] ...] ( positions 4+6, position 4+7 position6+7 and position 5+8)
You would probably want to use another function to sum and check at this point.
Now will do the same for sum of 3 elements (if any) and so on, having max loop set at number of original array (the resulting number could be the sum of all the elements in the array).
The resulting example would be [ [4], [4], [4], [2,2], [2,2],[2,2], [1,3]]
answered Mar 22 at 9:59
MbotetMbotet
6613
6613
add a comment |
add a comment |
function combinations(array)
return new Array(1 << array.length).fill().map(
(e1,i) => array.filter((e2, j) => i & 1 << j));
function add(acc,a)
return acc + a
combinations([2, 4, 45, 6, 0, 19]).filter( subarray => subarray.reduce(add, 0) == 51 )
output
[[2,4,45],[45,6],[2,4,45,0],[45,6,0]]
combinations([1, 11, 100, 1, 0, 200, 3, 2, 1, 280]).filter( subarray => subarray.reduce(add, 0) == 280 )
output
[[280],[0,280]]
add a comment |
function combinations(array)
return new Array(1 << array.length).fill().map(
(e1,i) => array.filter((e2, j) => i & 1 << j));
function add(acc,a)
return acc + a
combinations([2, 4, 45, 6, 0, 19]).filter( subarray => subarray.reduce(add, 0) == 51 )
output
[[2,4,45],[45,6],[2,4,45,0],[45,6,0]]
combinations([1, 11, 100, 1, 0, 200, 3, 2, 1, 280]).filter( subarray => subarray.reduce(add, 0) == 280 )
output
[[280],[0,280]]
add a comment |
function combinations(array)
return new Array(1 << array.length).fill().map(
(e1,i) => array.filter((e2, j) => i & 1 << j));
function add(acc,a)
return acc + a
combinations([2, 4, 45, 6, 0, 19]).filter( subarray => subarray.reduce(add, 0) == 51 )
output
[[2,4,45],[45,6],[2,4,45,0],[45,6,0]]
combinations([1, 11, 100, 1, 0, 200, 3, 2, 1, 280]).filter( subarray => subarray.reduce(add, 0) == 280 )
output
[[280],[0,280]]
function combinations(array)
return new Array(1 << array.length).fill().map(
(e1,i) => array.filter((e2, j) => i & 1 << j));
function add(acc,a)
return acc + a
combinations([2, 4, 45, 6, 0, 19]).filter( subarray => subarray.reduce(add, 0) == 51 )
output
[[2,4,45],[45,6],[2,4,45,0],[45,6,0]]
combinations([1, 11, 100, 1, 0, 200, 3, 2, 1, 280]).filter( subarray => subarray.reduce(add, 0) == 280 )
output
[[280],[0,280]]
answered Mar 22 at 10:57
paradoxparadox
457512
457512
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%2f55296323%2ffind-all-subarray-with-sum-equal-to-number%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
2
Not able to make out anything from the question
– brk
Mar 22 at 9:18
@brk as mentioned I am not getting subarray using my function
– user944513
Mar 22 at 9:20
@brk given an array of numbers and a target number, find the smallest possible section of the array that when summed equals the target number. I think, I don't know if it's supposed to be a subarray (so, preserving order of the elements) or any valid combination of the array elements.
– VLAZ
Mar 22 at 9:20
@user944513 What happens when the numbers cannot add up to that number
– nick zoum
Mar 22 at 9:22
5
Do you mean sub-array or sub-sequence? Because sub-array is contiguous, but sub-sequence isn't
– bird
Mar 22 at 9:28