Find all subarray with sum equal to number?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 JavaScriptFind the number of subarrays in an array
Blender - show edges angles “direction”
Can a Bard use an arcane focus?
In Star Trek IV, why did the Bounty go back to a time when whales were already rare?
What (else) happened July 1st 1858 in London?
Is there an wasy way to program in Tikz something like the one in the image?
How to prevent YouTube from showing already watched videos?
For airliners, what prevents wing strikes on landing in bad weather?
Why are all the doors on Ferenginar (the Ferengi home world) far shorter than the average Ferengi?
Is it legal to discriminate due to the medicine used to treat a medical condition?
How to check participants in at events?
Why isn't KTEX's runway designation 10/28 instead of 9/27?
Lifted its hind leg on or lifted its hind leg towards?
How do I repair my stair bannister?
What does the "3am" section means in manpages?
Freedom of speech and where it applies
Can I use my Chinese passport to enter China after I acquired another citizenship?
Is there a good way to store credentials outside of a password manager?
Can the electrostatic force be infinite in magnitude?
Can a controlled ghast be a leader of a pack of ghouls?
Is it okay / does it make sense for another player to join a running game of Munchkin?
What will be the benefits of Brexit?
Would it be legal for a US State to ban exports of a natural resource?
Partial sums of primes
Could solar power be utilized and substitute coal in the 19th century?
Find all subarray with sum equal to number?
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 JavaScriptFind the number of subarrays in an array
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,3881461124
3,3881461124
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)
sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = [];
for (var i=0; i<n; ++i)
dp[i] = []
dp[i][0] = true;
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;
// Fill rest of the entries in dp[][]
for (var i = 1; i < n; ++i)
for (var j = 0; j < sum + 1; ++j)
dp[i][j] = (arr[i] <= j) ? dp[i-1][j]
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
193k15107178
193k15107178
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,07321531
5,07321531
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
999620
999620
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,51511540
2,51511540
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)
sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = [];
for (var i=0; i<n; ++i)
dp[i] = []
dp[i][0] = true;
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;
// Fill rest of the entries in dp[][]
for (var i = 1; i < n; ++i)
for (var j = 0; j < sum + 1; ++j)
dp[i][j] = (arr[i] <= j) ? dp[i-1][j]
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)
sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = [];
for (var i=0; i<n; ++i)
dp[i] = []
dp[i][0] = true;
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;
// Fill rest of the entries in dp[][]
for (var i = 1; i < n; ++i)
for (var j = 0; j < sum + 1; ++j)
dp[i][j] = (arr[i] <= j) ? dp[i-1][j]
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)
sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = [];
for (var i=0; i<n; ++i)
dp[i] = []
dp[i][0] = true;
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;
// Fill rest of the entries in dp[][]
for (var i = 1; i < n; ++i)
for (var j = 0; j < sum + 1; ++j)
dp[i][j] = (arr[i] <= j) ? dp[i-1][j]
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)
sum < 0)
return;
// Sum 0 can always be achieved with 0 elements
dp = [];
for (var i=0; i<n; ++i)
dp[i] = []
dp[i][0] = true;
// Sum arr[0] can be achieved with single element
if (arr[0] <= sum)
dp[0][arr[0]] = true;
// Fill rest of the entries in dp[][]
for (var i = 1; i < n; ++i)
for (var j = 0; j < sum + 1; ++j)
dp[i][j] = (arr[i] <= j) ? dp[i-1][j]
printAllSubsets([1,2,3,4,5], 10);
edited Mar 22 at 14:46
answered Mar 22 at 10:03
MarcusMarcus
161111
161111
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
359113
359113
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
214310
214310
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
-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