algorithm - 查找整数数组中的元素，使得它们的和为 X 并且它们的平方和最小

Question

给定一个长度为 n 的数组 arr，找到 arr 中的所有元素，使得它们的总和为 x他们的平方和最小。我试图找到复杂度最低的算法。到目前为止，我已经编写了一个简单的递归算法，它可以找到数组中的所有子集并将总和检查作为基本条件。我写的代码是 javascript，如下所示:

var arr = [3, 4, 2, 1];
var arr2 = arr.map(function(n) { return n*n; });

var max_sum = 5;
var most_min = -1;

function _rec(i, _sum, _square) {
    if(_sum >= max_sum) {
        if(most_min == -1 || _square < most_min) {
            most_min = _square;
            console.log("MIN: " + most_min);
        }
        console.log("END");
        return;
    }

    if(i >= arr.length)
        return;

    console.log(i);
    var n = arr[i];
    // square of above number
    var n2 = arr2[i];    
    _sum = _sum + n;
    _square = _square + n2;
    _rec(i+1, _sum, _square);

    _sum = _sum - n;
    _square = _square - n2;
    _rec(i+1, _sum, _square);
}

_rec(0, 0, 0);

访问http://jsfiddle.net/1dxgq6d5/6/查看上述算法的输出。上面的算法很简单，就是在每个递归步骤中通过评估两个选择来找到所有子集； 1) 选择当前数字或 2) 拒绝，然后进行递归。

我正在尝试找到一种比上面的简单递归更有效的算法。任何建议或帮助将不胜感激。

另一个假设

我在想，如果我对数组进行排序，并找到具有最小方差(彼此之间的间隔)的元素子集，使得它们的总和为 x 将满足我的要求。不确定这是否会有很大帮助，但我目前正在努力改进我目前的盲递归方法。

Answer 1

首先，您查找的是子集，而不是排列，因为您不关心每个集合中元素的顺序。

其次，即使不尝试最小化平方和，仅查找是否存在总和为目标数的子集也是 NP 完全的——这就是 subset sum problem .目前大多数计算机科学家认为 P != NP，因此没有有效的(多项式时间)算法。