题解 | #数字和为sum的方法数#

这个题目让我感受到了算法的魅力。
写的第一个解法跑一个n = 684的用例，需要100个小时才能出结果；当放弃第一个解法另换思路后，第二个解法就可以满足题目要求，1秒内出结果。下面给出两种解法，但是只介绍第二种解法思想。
首先将n个数划分成两部分（代码中后缀用Left和Right表示），分别在这两部分中取数，计算和为0至sum的方案数（其中和为0的方案数固定为1（因为一个数都不取的这种方案，和为0）），将结果保存在两个大小为sum+1的数组中。根据这两个数组可以合成一个数组（合成方法见代码），这个数组中存放了n个数中取数，和为0至sum的方案数。输出和为sum的方案数即可。
第一种解法代码：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;


// 第一种解法，算法复杂度高
void mycalnumproposal(vector<int> avec, int sum, int &numproposal) {//这样做算法复杂度太大，跑示例得跑100多个小时，要求算法1秒内完成，可见优秀算法的必要和重要性
    if (sum == 0) { 
        numproposal++;
        return; 
    }
    int n = avec.size();

    vector<int> avectemp(avec);
    for (int k = 0; k < n; k++) { // 递归里面加循环不是明智的选择
        int sumtemp = sum - avec[k];
        if (sumtemp < 0)continue;//return;   // return对应排序序列；continue对应普通序列
        else {
            avectemp.erase(avectemp.begin(), avectemp.begin() + 1);
            mycalnumproposal(avectemp, sumtemp, numproposal);
        }
    }
}



int main() {
    int n, sum;
    int a;
    vector<int> avec;
    cin >> n >> sum;
    for (int i = 0; i < n; i++) {
        cin >> a;
        avec.push_back(a);
    }
    //sort(avec.begin(), avec.end()); // 排序也需要时间
    int numproposal = 0;
    mycalnumproposal(avec, sum, numproposal);

    cout << numproposal << endl;

    return 0;
}

第二种解法代码：

#include<iostream>
#include<vector>
using namespace std;



vector<long> mycalNumProposal2(vector<long> nvec, long sum) {
    vector<long> mvec(sum+1,0);mvec[0] = 1;
    if (nvec.size() == 1) {
        if(nvec[0] <= sum) mvec[nvec[0]] = 1;
        return mvec;
    }

    int k = nvec.size() / 2;
    vector<long> nvecLeft(nvec);
    nvecLeft.erase(nvecLeft.begin() + k, nvecLeft.end());
    vector<long> nvecRight(nvec);
    nvecRight.erase(nvecRight.begin(), nvecRight.begin() + k);

    vector<long> mvecLeft(sum+1, 0);
    vector<long> mvecRight(sum+1, 0);

    mvecLeft = mycalNumProposal2(nvecLeft, sum);
    mvecRight = mycalNumProposal2(nvecRight, sum);

    for (long i = 1; i <= sum; i++) {
        for (long j = 0; j <= i; j++) {
            mvec[i] += mvecLeft[j] * mvecRight[i - j];
        }
    }
    mvec[0] = 1;
    return mvec;

}
int main() {
    int n;
    long sum;
    long a;
    vector<long> nvec;
    cin >> n >> sum;
    for (long i = 0; i < n; i++) {
        cin >> a;
        nvec.push_back(a);
    }
    vector<long> mvec;
    mvec = mycalNumProposal2( nvec, sum);
    cout << mvec[sum] << endl;
    return 0;
}