Brute-Force algorithm in C++ I wrote a brute-force algorithm which shall find all possible combinations of ASCII-values that can sum up to a specific value (int hashval). 

The algorithm is derived from a recursive algorithm that could print all binary numbers that are possible within a specific length characters. I modified it, so it now iterates over all ints between first and last, thus building all combinations there are. If the sum of the combination is equal to hashval, then the combination is saved in vector&lt;vector&lt;int[]&gt;&gt; combinations. When all possible combinations are found the content of combinations is printed into a file.

I already use some little tricks I learned for competitive programming, but the algorithm is still too slow. At the moment it is running for approximately 3 hours for no more than 13 characters, with no end in sight, file I/O hasn't even started yet. I know that its Big-O for runtime is horrible, no doubt. (if I get it right it is O(m^n) ).

I considered adding a check for n=1 since that would leave only one possibility for the last character, saving some recursive calls, but that would add another if to be called in every function call, either.

What more ways are there to improve the speed? Any improvements are not bound to C++, I will take a look at every programming language which might be more efficient in this case, though I guess there scarcely will be one.

The algorithm:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;bits/stdc++.h&gt;
#include &lt;cstdio&gt;

using namespace std;
using namespace std::chrono;

//values in decimal
int first = 32, last = 126, characters = 13, hashval = 1207;

vector&lt;vector&lt;int&gt;&gt; combinations;

void brute(int n, int it, vector&lt;int&gt; values) {
    if (n == 0) {
        int sum = 0;

        //sum up recent values
        for (int j = 0; j &lt; characters; ++j) {
            sum += values[j];
        }
        //save values if matching to hash
        if (sum == hashval) {
            combinations.push_back(values);
        }
    } else {
        for (int i = first; i &lt;= last; ++i) {
            values[it] = i;
            brute(n - 1, it + 1, values);
        }
    }
}


Printing the output to a file:

void printToFile(){
    freopen("fileContent.brute", "w", stdout);
    cout &lt;&lt; "\n\nFound " &lt;&lt; combinations.size() &lt;&lt; " combinations." &lt;&lt; endl;
    int counter = 0;
    for (auto combo = combinations.begin(); combo != combinations.end(); ++combo){
        for (int i = 0; i &lt;  characters; ++i) {
            cout &lt;&lt; (char) combinations.at(counter).at(i) &lt;&lt; " ";
        }
        cout&lt;&lt; "\r\n";
        counter++;
    }
}


The main-method:

int main() {
    auto start = high_resolution_clock::now();
    //characters = 3, first = 0, last = 3, hashval = 6;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector&lt;int&gt; values;

    for (int i = 0; i &lt; characters; ++i) {
        values.push_back(first);
    }

    brute(characters, 0, values);

    printToFile();
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast&lt;seconds&gt;(stop - start);
    cout &lt;&lt; "Brute-forcing needed " &lt;&lt; duration.count() &lt;&lt; " seconds.\r\n";

    cout.flush();

    return 0;
}
Use a better container

The main issue is that std::vector&lt;int&gt; is a bad container for storing a set of ASCII characters. Every vector allocates on the heap, and an empty vector is likely 24 bytes in size. So this is huge waste. Why not use a container designed to hold a series of ASCII characters, like... std::string!

Do you need to store all possible combinations in memory?

You are first building a vector of all possible combinations with the desired sum. But the only thing you are doing with it afterwards is writing the result to a file. That's a huge waste of memory, and maintaining the vector of vectors in itself costs some CPU time as well. Why not write the results to a file immediately?

Exit early when your combination has already exceeded the desired sum

You always try to fill the vector values with characters elements, and try each possible element at each position. However, in brute(), you should calculate the partial sum of elements 0 up to n, and then just check in the for loop whether adding i to that sum would be equal to or higher than the desired sum. If so, if it's equal output the combination, but in any case return at that point instead of trying other values.

Use \n consistently to end lines

You are mixing \n, \r\n and std::endl in your code. Stick to \n, it is the standard way of ending a line in C and C++. The underlying I/O routines will automatically convert the newlines to \r\n on Windows.

std::endl is equivalent to \n plus a call to flush(). Unless there is a good reason to, you don't want this extra flushing to happen, since it reduces the performance of your program. Normally, std::cout is line-buffered, so if something ends with a \n, it is already flushed automatically. This also means you should remove the explicit call to cout.flush().