c++ - 代码优化子集总和

Question

这是我的代码，它打印总和等于给定总和的子集元素(它仅适用于正数):

#include <bits/stdc++.h>
using namespace std;

void traverse(vector<int> vec) {
    for(int a=0; a < vec.size(); a++)
        cout << vec[a] << " ";
    cout << endl;
}

void possible(vector<int> vec, int sum, vector<int> now) {
    if(sum == 0) {
        traverse(now);
    }
    else if(sum < 0) {
        now.clear();
    }
    else if(sum > 0 && vec.size() > 0) {
        for(int a = 0; a < vec.size(); a++) {
            now.push_back(vec[a]);
            vector<int> vecc(vec.begin() + a + 1, vec.end());
            possible(vecc, sum - vec[a], now);
            now.erase(now.end() - 1);
        }
    }
}

int main() {
    int n, sum;
    cin >> n >> sum;

    vector<int> vec(n), now;
    for(int a = 0; a < n; a++)
        cin >> vec[a];

    possible(vec, sum, now);
    return 0;
}

是否有改进的机会或任何更快的方法来缩短运行时间？

对此有任何动态问题解决方案吗？

Answer 1

子集和问题可以通过动态规划来解决，您可以在 Dynamic Programming | Set 25 (Subset Sum Problem) 中阅读.

该问题实际上是 NP 完全问题(此问题没有已知的多项式时间解决方案)。上面的链接提供了两种解决方案，其中第二种可以在伪多项式时间内解决问题。

---

作为一项技术优化，您可以更改此设置:

void traverse(vector<int> vec)

为此:

void traverse(vector<int>& vec)

为了避免不必要的拷贝，可能很大， vector 。如果可以，请为所有功能执行此操作。

---

在启用警告的情况下编译您的代码(例如 GCC 的 -Wall -Wextra)，并修复这些警告。然后考虑性能。

---

附言:Why should I not #include <bits/stdc++.h>?