c++ - 元素的每一个和的可能性

Question

从一个给定的数组(称之为numbers[])，我想要另一个数组(results[])，它包含第一个数组的元素之间的所有可能的总和。

例如，如果我有 numbers[] = {1,3,5}，results[] 将为 {1,3,5,4,8,6,9,0}。有 2^n 种可能性。一个数字是否出现两次并不重要，因为 results[] 将是一个 set。

我为成对或三元组的总和做了这件事，这很容易。但是我不明白当我们对 0、1、2 或 n 个数字求和时它是如何工作的。

这就是我为配对所做的:

std::unordered_set<int> pairPossibilities(std::vector<int> &numbers) {
    std::unordered_set<int> results;
    for(int i=0;i<numbers.size()-1;i++) {
        for(int j=i+1;j<numbers.size();j++) {
            results.insert(numbers.at(i)+numbers.at(j));
        }
    }
    return results;
}

此外，假设 numbers[] 已排序，是否有可能在我们填充 results[] 时对它进行排序？

谢谢!

Answer 1

这可以通过 Dynamic Programming (DP) 来完成在 O(n*W) 中，其中 W = sum{numbers}。

这与Subset Sum Problem的解决方案基本相同，利用问题具有最优子结构这一事实。

DP[i, 0] = true
DP[-1, w] = false          w != 0
DP[i, w] = DP[i-1, w] OR DP[i-1, w - numbers[i]]

首先按照上述解决方案找到DP[n, sum{numbers}]。

结果，您将获得:

DP[n , w] = true 当且仅当 w 可以从 numbers 构造