我如何递归枚举加到给定总和上的所有子集？ [关闭]

Question

关闭。这个问题需要details or clarity。它当前不接受答案。

---

是否要改善此问题？通过editing this post添加详细信息并澄清问题。

已关闭1小时前。

[当我尝试获取输出时，它会在使用相同元素之前显示几次相同的解决方案，然后再进行另一次尝试。

我想从等于和的数组中获得不同的解决方案

例如，

解决方案1 ​​= 14，8

解决方案2 = 14，5，3

解决方案3 = 13，9

依此类推，但得到的是22个总数的重复解决方案。您可以将此代码复制并粘贴到Visual Studio中，以了解我的意思。我不知道是什么原因导致此错误

#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <algorithm>


using namespace std;




void printSolution(int* r, int k)
{
    cout << " Solution : { ";
    for (int j = 0; j < k; j++)
        {
        cout << r[j]; 

        if (j < k - 1)
            cout << ", ";


    }

    cout << " }" << endl;

}

bool subSetSum(int* a, int n, int i, int sum, int* r, int k)
{
    if (sum == 0)
        printSolution(r, k);
    if (i > n)
        return false;

    r[k++] = a[i];

    if (subSetSum(a, n, i + 1, sum - a[i], r, k))
        return true;

    k -= 1;
    subSetSum(a, n, i + 1, sum, r, k);

}

int descendingOrder(const void* a, const void* b)
{
    int* p1 = (int*)a;
    int* p2 = (int*)b;
    return *p2 - *p1;
}

int main()
{
    int a[] = { 4, 10, 7, 12, 6, 10, 10, 8, 5, 13, 13, 11, 3, 14 };
    int n = 14;

    int* r = new int[n];
    int k = 0;


    qsort(a, n, sizeof(int), descendingOrder);

    cout << " Array a[] = ";

    for (int count = 0; count < n; count++)
    {
    cout << a[count] << "  ";
    }

    cout << endl << endl;
    int sum = 22;

    bool solFound = subSetSum(a, n, 0, sum, r, k);

    return 0;
}

Answer 1

首先，由于这个问题是NP完全的，因此此处不能（可能）应用效率，这意味着它在多项式时间内可能无法解决。

关于解决方案，我将附上代码：

using SolutionT = std::vector<std::set<std::size_t>>;

SolutionT subsetSum(const std::vector<int>& array, int requiredSum, std::size_t index, int currentSum)
{
    if (currentSum > requiredSum) { // Remove it if negative integers are present
        return {};
    }

    if (index >= array.size()) {
        return {};
    }

    if (requiredSum == currentSum + array[index]) {
        std::set<std::size_t> indices{};
        indices.insert(index);
        SolutionT solution;
        solution.emplace_back(std::move(indices));
        return solution;
    }

    auto includedSolutions = subsetSum(array, requiredSum, index + 1, currentSum + array[index]);
    for (auto& solution : includedSolutions) {
        solution.insert(index);
    }

    auto excludedSolutions = subsetSum(array, requiredSum, index + 1, currentSum);

    std::copy(std::make_move_iterator(includedSolutions.begin()),
              std::make_move_iterator(includedSolutions.end()), 
              std::back_inserter(excludedSolutions));
    return excludedSolutions;
}

SolutionT subsetSum(const std::vector<int>& array, int requiredSum)
{
    return subsetSum(array, requiredSum, 0, 0);
}

代码相当复杂，因为您需要成倍数量的元素，因此没有C ++容器很难做到。