I'm taking in an array of numbers [4, 6, 23, 10, 1, 3] I need to return true if any combinations of numbers in the array add up to the largest number in the array. So the example above should return true because 3 + 4 + 6 + 10 = 23
My thought behind this problem is I should first put the array in numerical order then make a new array with just the numbers I'm adding because I'm not adding the largest number. Then I need some method that says "If any combination of adding these numbers together equals the largest number in the original array return true". This is the code I've written so far, but I'm stuck on the for loop.. Any help would be very much appreciated!
function ArrayChallenge(arr){
let order = arr.sort(function(a, b){return a-b})
let addThese = order.slice(0,order.length-1)
for(i = 0; i < addThese.length-1; i++){
return true
}
}
console.log(ArrayChallenge([3,5,-1,8,12]))
It seems like a trick question. Here's the answer:
function ArrayChallenge(arr){
return true
}
Because the sum of just the largest number is always equal to the largest number.
If this solution is somehow not allowed, see subset sum problem:
there is a multiset S of integers and a target-sum T, and the question is to decide whether any subset of the integers sum to precisely T.
The most straightforward solution to that problem is with recursion; something like this:
function subsetSum(arr, sum) {
if (arr.length == 0) {
// No numbers left in the array. The only sum we can make is 0.
// If that is the sum we are seeking, great!
return sum == 0
} else {
// We will try both using and not using the first number in the array.
// The rest is passed to the recursive call.
const [current, ...remaining] = arr
return (
// Exclude current number, and recurse. We have to make the full
// sum with the remaining numbers.
subsetSum(remaining, sum) ||
// Include current number, meaning we have sum - current left
// to make with the remaining numbers.
subsetSum(remaining, sum - current)
)
}
}