Задача на полный перебор не прошла по времени C++

Условие задачи:

Даны 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";
     
}