Перебор всех возможных сумм массива с++

236

26 июня 2018, 22:20

Помогите с алгоритмом для программы

Есть массив из n чисел, необходимо создать новый массив, в котором будут выведены все суммы исходного массива.

Например:

На вход:

3
2 3 5

На выход:

2 3 5 5 7 8 10

На вход:

4 
6 7 2 10

На выход:

6 7 2 10 13 8 16 9 17 12 15 23 19 25

Понимаю, что нужно использовать рекурсию, но не знаю, как это сделать

Answer 1

Один из возможных классических подходов перебора - это использование рекурсии. Вот код, который рекурсивно считает суммы всех возможных комбинаций массива

#include <iostream>
#include <vector>
int sum(std::vector<int>& result, const std::vector<int>& v, int index, int curSum)
{
    if (index < v.size())
    {
        curSum += v[index];
        for (int i = index + 1; i < v.size(); ++i)
        {
            int res = sum(result, v, i, curSum);
            result.push_back(res);
        }
    }
    return curSum;
}
int main()
{
    std::vector<int> v = { 6, 7, 2, 10 };
    std::vector<int> result;
    for (int i = 0; i < v.size(); ++i)
    {
        int res = sum(result, v, i, 0);
        result.push_back(res);
    }
    for (const int s : result)
        std::cout << s << " ";
    std::cout << std::endl;
}

На выходе имеем:

25 15 23 13 18 8 16 6 19 9 17 7 12 2 10

Answer 2

Выписка возможных выборок имеет сложность экспоненциальную O(2^N). Можно представлять конкретную выборку как массив логических значений true/false. Например как std::vector<bool>. Перебор возможных выборок с помощью рекурсии нагружает стек лишней информацией. Можно перебирать все выборки с помощью собственной процедуры инкремента {0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}. Те , кто дружит с языком C не любят вектора. Они пользуются массивом unsigned int m[(N / (sizeof(unsigned int)*8))+1]. Если аккуратно написать инкремент данного вектора, это даст максимальную скорость.