Как мне рекурсивно перечислить все подмножества, добавляемые к заданной сумме? - PullRequest
Новая
       93

Как мне рекурсивно перечислить все подмножества, добавляемые к заданной сумме?

0 голосов
/ 12 апреля 2020

Когда я пытаюсь получить вывод, он показывает одни и те же решения с одним и тем же элементом несколько раз, прежде чем перейти к другому.

Я хочу получить различные решения из массива, равного сумме

Например,

Решение 1 = 14, 8

Решение 2 = 14, 5, 3

Решение 3 = 13, 9

и так далее, но я получаю повторные решения на сумму 22. Я получаю эту ошибку

Решение : {14, 8}

Решение: {14, 8}

Решение: {14, 8}

Решение: {14, 8}

Решение: {14, 8}

Решение: {14, 8}

Решение: {14, 5, 3}

Решение: {13, 6, 3 }

Решение: {13, 5, 4}

Решение: {13, 5, 4}

Решение: {13, 6, 3}

Решение: {13, 5, 4}

Решение: {13, 5, 4}

и еще 20 строк одного и того же выхода. 

#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;
}

Ответы [ 2 ]

1 голос
/ 12 апреля 2020

У вас есть несколько ошибок в вашей функции subsetSum. Прежде всего, ваша версия имеет ветку, в которой она не возвращает значение. Это могло бы быть легко смягчено с помощью , включившего предупреждения компилятора .

Во-вторых, у вас возникла ошибка в состоянии прерывания. i==n - недопустимый индекс, поэтому вы перезапустите конец буфера.

Причина, по которой вы получаете один и тот же результат несколько раз, заключается в том, что существует несколько путей к одному и тому же результату. Скорее всего, это связано с отсутствующим оператором возврата.

Исправление для этого заключается в прекращении спуска рекурсии, как только вы найдете совпадение (при его печати). Гарантируется, что вы не найдете дополнительных результатов (если в ваших входах нет записей <= 0). 

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

    r[k] = a[i];

    bool found = subSetSum(a, n, i + 1, sum - a[i], r, k + 1);

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

    return found;
}

Обратите внимание, что при этом все равно будут найдены повторяющиеся решения для дублированных значений во входном массиве (например, 10). Вы можете легко добавить проверку, чтобы пропустить дублирующиеся значения во втором рекурсивном вызове в subSetSum, не передавая i + 1, но найдя следующий индекс, который не является дубликатом. Поскольку вы уже отсортировали свои входные данные, это можно сделать, увеличив значение i до тех пор, пока оно не укажет на другое значение.

Также следует отметить, что это довольно unidiomati c C ++. Лучший интерфейс для вашего subsetSum будет выглядеть так: 

template <typename T, typename ConstIterator>
bool subSetSum(ConstIterator begin, ConstIterator end, T sum, std::vector<T>& buf);

template <typename T, typename ConstIterator>
bool subSetSum(ConstIterator begin, ConstIterator end, T sum) {
  std::vector<T> buf;
  return subSetSum(begin,end,std::move(T),buf);
}
0 голосов
/ 12 апреля 2020

Прежде всего, никакая эффективность не может быть применена здесь (вероятно), так как этот вопрос является 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 ++ очень сложно обойтись .

...