这可以被视为一个优化问题，非常适合动态规划 https://en.wikipedia.org/wiki/Dynamic_programming.
这意味着您可以将其分解为递归，尝试找到越来越小的数组的最小长度，并根据已删除的内容调整总和。如果你的数组是[10, 0, -1, 20, 25, 30]总和为59你可以将最短视为min of:
[10, ... shortest([ 0, -1, 20, 25, 30], 49)
[0, ... shortest([10, 20, 25, 30], 49), 59)
[-1, ... shortest([10, 0, 20, 25, 30], 60)
... continue recursively
每次递归，数组都会变短，直到只剩下一个元素。那么问题是该元素是否等于所有减法后剩下的数字。
用代码更容易显示：
function findMinSum(arr, n){
if(!arr) return
let min
for (let i=0; i<arr.length; i++) {
/* if a number equals the sum, it's obviously
* the shortest set, just return it
*/
if (arr[i] == n) return [arr[i]]
/* recursively call on subset with
* sum adjusted for removed element
*/
let next = findMinSum(arr.slice(i+1), n-arr[i])
/* we only care about next if it's shorter then
* the shortest thing we've seen so far
*/
if (next){
if(min === undefined || next.length < min.length){
min = [arr[i], ...next]
}
}
}
return min && min /* if we found a match return it, otherwise return undefined */
}
console.log(findMinSum([10, 0, -1, 20, 25, 30], 59).join(', '))
console.log(findMinSum([10, 0, -1, 20, 25, 30], 29).join(', '))
console.log(findMinSum([10, 0, -1, 20, 25, 30], -5)) // undefined when no sum
这在计算上仍然相当昂贵，但应该是much比查找所有子集和总和更快。
