Условие задачи:
Даны N целых чисел X1, X2, …, XN. Требуется расставить между ними знаки «+» и «-» так, чтобы значение получившегося выражения было равно заданному целому S.
Входные данные Входной файл INPUT.TXT в первой строке содержит числа N и S. В следующей строке располагается N чисел, разделенных пробелом. Ограничения: 2 ≤ N ≤ 24, 0 ≤ Xi ≤ 5*10^7, -10^9 ≤ S ≤ 10^9.
Выходные данные В выходной файл OUTPUT.TXT выведите «No solution», если такой результат получить невозможно, иначе выведите получившееся равенство. Если решение не единственное, выведите любое.
Ну первые мои мысли при данной задаче: N у нас достаточно маленькое, а значит вполне можно перебрать все возможные случаи расстановок знаков. Ну и методом "вдумчивого взгляда" можно понять, что жадный алгоритм тут придумать невозможно. Поэтому я реализовал полный перебор:
#include<iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
string ans;
//функция генерации всех возможных сумм
void generate(const ll& need, ll sum_now, const vector<ll>& a, ll i, string str)
{
if (i == a.size())
{
if (need == sum_now)
{
ans = str;
}
}
if (i < a.size())
{
generate(need, sum_now + a[i], a, i + 1, str + "+" + to_string(a[i]));
generate(need, sum_now - a[i], a, i + 1, str + "-" + to_string(a[i]));
}
}
int main()
{
ll n, s;
cin >> n >> s;
vector<ll> a(n);
for (auto& x : a)
cin >> x;
//a[0] может быть только положительным, поэтому сразу вставляем его в сумму
generate(s, a[0], a, 1, to_string(a[0]));
if (ans.empty())
cout << "No solution" << endl;
else
cout << ans + "=" + to_string(s) << endl;
}
И данное решение не прошло по времени. И не совсем понятно почему. Всего вариантов перебора 2^23 < 10^7. По идее должно быть быстро. Встает два вопроса:
Можно ли как-то в случае нахождения верного ответа сказать программе завершить все вызовы рекурсий сразу и закончить работу функции? У меня конечно есть мысль, что можно написать return, но по факту мы же только 1 из вызывов завершаем? Будет ли завершать эта версия выполнять это:
void generate(const ll& need, ll sum_now, const vector<ll>& a, ll i, string str)
{
if (i == a.size())
{
if (need == sum_now)
{
ans = str;
return;
}
}
if (i < a.size())
{
generate(need, sum_now + a[i], a, i + 1, str + "+" + to_string(a[i]));
generate(need, sum_now - a[i], a, i + 1, str + "-" + to_string(a[i]));
}
}
Естественно по идее данная оптимизация не сильно поможет, потому что самая долгая работа все равно будет в случае если должно вывестись "No solution" а значит перебор всех случаев неизбежен. Как можно оптимизировать мой алгоритм?
Встает вопрос, существует ли итеративное решение к данной задаче, а не рекурсивное? Просто мыслей к нему нет никаких, если дадите подсказки буду рад.
Код решения Harry, который тоже чуть чуть не прошел (см ответ Harry и комментарии к нему):
#include<iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
ll n, s;
cin >> n >> s;
vector<ll> a(n);
for (auto& x : a)
cin >> x;
int M = 1 << (n - 1);
for (size_t i = 0; i < M; i++)
{
ll sum = a[0];
int m = i;
for (size_t j = 1; j < n; j++)
{
if (m & 1)
sum += a[j];
else
sum -= a[j];
m >>= 1;
}
if (sum == s)
{
cout << a[0];
m = i;
for (size_t j = 1; j < n; j++)
{
if (m & 1)
cout << "+" << a[j];
else
cout << "-" << a[j];
m >>= 1;
}
cout << "=" << s;
return 0;
}
}
cout << "No solution";
}
как сделать иначе
в рамках минимального изменения вашего рекурсивного решения - передавать вместо строки 32-битовое число, устанавливая очередной бит в 0 или 1. При нахождении решения расшифровываете эти биты в плюсы-минусы. Про Грея - да, код может быть полезен при итеративном решении.