獲取等於目標的數組項的總和（子集總和）

Question

我需要獲取與目標相等的數組項的總和。如果數組項的總和不等於目標，我希望得到小於目標的最高總和。

下面是一個例子：

輸入： [4，6，8，12，4,6，6，12，4，4,4]

結果： [ ] [] [8,4] [6,6] [4,4,4] [6,4]

注：陣列項只能使用一次。

目前這裏是我現在所擁有的：

var subset_sum = function (items, target) { 
    var results = []; 

    items.sort(function (a, b) { return b - a }); 

    ss = function (items) { 
     var item = items.shift(); 
     if (item < target) { 
      var perms = []; 
      perms.push(item); 
      var isItemPush = false; 

      var counter = 0 
      var innerSubset = function() { 
       if (item + items[counter] === target) { 
        perms.push(items[counter]) 
        items.splice(counter, 1); 
        results.push(perms); 
        isItemPush = true; 
       } else { 
        if (counter < items.length) { 
         counter += 1; 
         innerSubset(); 
        } 
       } 
      } 

      innerSubset(); 

     } else { 
      results.push(item); 
     } 

     if (items.length === 0) { 
      return results; 
     } 

     return ss(items); 
    } 
    return ss(items) 
} 

window.onload = function() { 
    var items = [4, 6, 8, 12, 4, 6, 6, 12, 4, 4]; 
    target = 12; 

    result = subset_sum(items, target); 
    console.log(result); 
} 

這種方法的問題是，它僅僅是一維或二維。從上面的例子，它不返回的結果[4,4,4]和6

Answer 1

非常相似溶液到你的，有點不清楚，如果它是有幫助的：

numbers = [4, 6, 8, 12, 4, 6, 6, 12, 4, 4]; 

var result = createSubsets(numbers, 12); 

console.log('Result', JSON.stringify(result)); 

function createSubsets(numbers, target) { 
    // filter out all items larger than target 
    numbers = numbers.filter(function (value) { 
     return value <= target; 
    }); 

    // sort from largest to smallest 
    numbers.sort(function (a, b) { 
     return b - a; 
    }); 

    // array with all the subsets 
    var result = []; 

    while (numbers.length > 0) { 
     var i; 
     var sum = 0; 
     var addedIndices = []; 

     // go from the largest to the smallest number and 
     // add as many of them as long as the sum isn't above target 
     for (i = 0; i < numbers.length; i++) { 
      if (sum + numbers[i] <= target) { 
       sum += numbers[i]; 
       addedIndices.push(i); 
      } 
     } 

     // remove the items we summed up from the numbers array, and store the items to result 
     // since we're going to splice the numbers array several times we start with the largest index 
     // and go to the smallest to not affect index position with splice. 
     var subset = []; 
     for (i = addedIndices.length - 1; i >= 0; i--) { 
      subset.unshift(numbers[addedIndices[i]]); 
      numbers.splice(addedIndices[i], 1); 
     } 
     result.push(subset); 
    } 

    return result; 
} 

可生產陣列：

[12],[12],[8,4],[6,6],[6,4],[4,4] 

子集長度沒有限制。如果你增加一個4到數字數組，你會得到結果：

[12],[12],[8,4],[6,6],[6,4],[4,4,4] 

的jsfiddle：http://jsfiddle.net/kUELD/