目標是創建一個以數字陣列作為引數的函式，并檢查是否可以將其中最大的數字作為陣列中任何其他數字的總和來獲得。
一個條件是負數可以作為引數的陣列的一部分。
問題
我想出的函式對除最大陣列成員之外的所有陣列成員求和，而不是對其中任何一個成員求和。這就是它失敗的原因，如下所示
function ArrayAddition(arr) {
// Sort small to large
arr = arr.sort((a, b) => a - b);
// get maximum number
var max = arr.pop();
// Sum
var num = 0;
arr.forEach((item) => {
num = item
});
return max === num;
}
// Correctly return true
console.log(ArrayAddition([5,7,16,1,3]));
// Wronglly retuns false (5 - 2 8 = 11)
console.log(ArrayAddition([2,5,-2,8,11]));問題
如果任何陣列成員的總和最大，我怎樣才能使它作業？
uj5u.com熱心網友回復：
從陣列中洗掉最大元素后，任務現在變為給定陣列和目標總和（最大元素），查找陣列中是否存在總和為目標總和的任何子序列。此問題與子集和問題相同
解決這個問題的最簡單方法是使用包含排除原則并O(2^n)按照 Mihail 的回答已經建議的方式解決它。還有其他方法可以更有效地解決它（查看子集和問題鏈接）
在下面的方法中，我們只考慮所有這些子集的總和，而不是生成所有可能的子集。這將節省大量記憶體，但最壞的時間復雜度仍然保持不變，即O(2^n).
function ArrayAddition(arr) {
// Sort small to large
arr = arr.sort((a, b) => a - b);
// get maximum number
const max = arr.pop();
// maintain a set of all possible sums
const sums = new Set();
// insert 0 into sums set i.e, sum of an empty set {}
sums.add(0);
for (const value of arr) {
const newSums = new Set();
for (const sum of sums) {
// new possible sum if we consider the value in a subset
const newSum = sum value;
// we have a subset whose sum is equal to max
if (newSum === max)
return true;
newSums.add(newSum);
}
// insert all new possible sums
for (const sum of newSums)
sums.add(sum);
}
// no subset which adds up to max was found
return false;
}
console.log(ArrayAddition([5, 7, 16, 1, 3]));
console.log(ArrayAddition([2, 5, -2, 8, 11]));舉例說明方法
arr = [5,7,16,1,3]
after sorting and removing the max element we have
arr = [1,3,5,7]
max = 16
now initially the set 'sums' only has 0 (empty set)
sums = { 0 }
after the first iteration
sums = {0, 1} which is {[0], [0 1]}
after the second iteration
sums = {0, 1, 3, 4} which is {[0], [0 1], [0 3], [0 1 3]}
after third iteration
sums = {0, 1, 3, 4,
5, 6, 8, 9}
after fourth iteration
sums = {0, 1, 3, 4, 5, 6, 8, 9
7, 8, 10, 11, 12, 13, 15, 16}
since 16 is a possible sum, we return true
uj5u.com熱心網友回復：
下面是一種使用位掩碼生成集合的所有子集的可能方法（并且是幼稚的）。您應該能夠將其用于正確的解決方案。通過減少記憶體使用和提前退出來進一步優化它將是一個很好的練習。
function allSubsetsWithBitmasks(arr) {
const n = arr.length;
const subsets = [];
// there are 2^n subsets for every set
// every subset can be represented by n bits
for (let i = 0; i < Math.pow(2, n); i ) {
const subset = [];
for (let j = 0; j < n; j ) {
// if j-th bit is on, include arr[j] in the subset
if (i & (1 << j)) subset.push(arr[j]);
}
subsets.push(subset);
}
return subsets;
}
console.log(allSubsetsWithBitmasks([1, 2, 3, 4]));
我鼓勵您也撰寫回溯解決方案并擺脫 .sort() 因為它引入了不必要的對數因子。（排序是在O(N log N)）。
uj5u.com熱心網友回復：
我喜歡這類問題……讓我想起了大學時代。對于這個，不確定為什么所有這些答案都涉及復雜的集合和子集。真正的問題是“陣列中是否存在某種數字組合，當求和時，它等于最大數字。
下面的解決方案將使用遞回函式對陣列的所有組合求和。如果它沒有找到可能的 sum = max，它會開始一個一個地從陣列中剔除元素，并每次檢查是否存在總和為最大值的組合。
** 注意 - 從最小到最大排序陣列是絕對必要的
let arNum = [1, 1, 3, 5, 7, 9];
console.log(canSumToLargest(arNum));
function canSumToLargest(arNum){
let bCanSum = false;
let nMax = arNum.sort((a, b) => a - b).pop();
// traverse each element checking if it can sum to max
arNum.forEach((ele, i) =>{
let arTmp = arNum.slice();
let nSum = arTmp.splice(i, 1)[0];
// check for possible sum = max
if(hasSum(arTmp, nMax, nSum, 0)){
bCanSum = true;
return false // jump out of foreach loop
}
// no max sum at this point. so begin removing numbers one by one
else{
for(let n = 0, nLen = arTmp.length; n < nLen; n ){
arTmp.shift();
if(hasSum(arTmp, nMax, nSum, 0)){
bCanSum = true;
return false // jump out of foreach loop
}
}
}
});
return bCanSum
}
// recursive array summing function.
// sums all elements one by one until max found, or sum is larger than max, or reached end of array
function hasSum(arr, nMax, nSum, nNdx){
if(nNdx == arr.length)
return false
nSum = arr[nNdx];
if(nSum == nMax)
return true
return hasSum(arr, nMax, nSum, nNdx 1)
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/505896.html
標籤：javascript 数组 算法 排序