Partitions of a number (backtracking) - time efficiency

Question

I had to write an algorithm that prints the partitions of a natural number in lexicographic order. Example of I/O:

If the algorithm reads from partitiinumar.in.txt n=5

In partitiinumar.out.txt we should have:

1 1 1 1 1

1 1 1 2

1 1 3

1 2 2

1 4

2 3

5

The problem is that I have a time limit for the execution of the algorithm of 0.5 sec and for values of n higher than 9 (1<=n<=40), the exection time increases a lot, so I have to optimize the code. I ask for some time efficiency suggestions. Here is the code:

#include <fstream>

using namespace std;

ofstream out("partitiinumar.out.txt");

int n, solutions[41];


int solution(int k)          
{
    int S = 0;
    for (int i = 1; i < k; i++)
        S = S + solutions[i];

    if (S == n)
        return 1;
    else
        return 0;
}

int succesor(int k)
{
    if (solutions[k] < n)
    {
        solutions[k]++;
        return 1;
    }
    else
        return 0;
}

int valid(int k)    // I guess that this function is the reason for the lack of efficiency. I created this function to select only the solutions that have the numbers in a increasing order
{
    if (k > 1)
        if (solutions[k] >= solutions[k - 1])
            return 1;
        else
            return 0;

    else return 1;
}

void backtracking(int k)
{
    if (solution(k))
    {
        for (int i = 1; i < k; i++)
            out << solutions[i] << " ";
        out << '\n';
    }
    else if (solution(k)==0 && k<=n)
    {
        solutions[k] = 0;
        while (succesor(k))
            if (valid(k))
                backtracking(k + 1);
    }

}

int main()
{
    ifstream in("partitiinumar.in.txt"); in >> n; in.close();

    if (n >= 1 && n <= 40)
        backtracking(1);

    out.close();

    return 0;
}

Answer 1

Nitpicks

using namespace std;

See also Why is “using namespace std;” considered bad practice?

ofstream out("partitiinumar.out.txt");

int n, solutions[41];

As a general rule, it is bad practice to use global variables. Obviously it won't make much difference in this program, but it's a bad habit to develop. Given that this is C++, you could put all the functions other than main inside a class and make these member variables. That would allow you to use them across multiple functions.

int solution(int k)          
{
    int S = 0;
    for (int i = 1; i < k; i++)
        S = S + solutions[i];

The last line would be more idiomatic as

        S += solutions[i];

And a little shorter.

    if (S == n)
        return 1;
    else
        return 0;
}

I would prefer

    if (S == n)
    {
        return 1;
    }
    else
    {
        return 0;
    }

as it makes it clearer what belongs with what. A side effect is that it makes certain types of bugs less likely.

But in this case, it's even easier to just say

    return S == n;

Rather than building an if/else to return the same thing.

However, I would actually do

    return S;

The problem is that there are really three states here but the function merges two of them into one. The values in the solution can sum to be less than, greater than, or equal to n. More about this later.

Performance

void backtracking(int k)
{
    if (solution(k))
    {
        for (int i = 1; i < k; i++)
            out << solutions[i] << " ";
        out << '\n';
    }
    else if (solution(k)==0 && k<=n)
    {
        solutions[k] = 0;
        while (succesor(k))
            if (valid(k))
                backtracking(k + 1);
    }

}

You engage in more backtracking than necessary. For example, it tries "1 1 1 1 2" as a solution and then tries "1 1 1 1 3". But "1 1 1 1 3" is farther from being a solution than "1 1 1 1 2". So why keep trying? If you change solution to return S instead of S == n, then you can change as follows.

void backtracking(int k)
{
    int sum = solution(k);
    if (sum == n)
    {
        for (int i = 1; i < k; i++)
            out << solutions[i] << " ";
        out << '\n';
    }
    else if (sum < n)
    {
        solutions[k] = 0;
        while (succesor(k))
            if (valid(k))
                backtracking(k + 1);
    }
}

Doing this dropped from 90 wrong solutions to 31 for when n equals 5. When n equals 9, it reduces from 18,546 wrong solutions to 356. Even this code finds over five million wrong solutions when n is 40. I'm guessing that the original code finds more, as when I ran it online, it timed out at five seconds even though counting the wrong solutions from this variant only took .12 seconds. Note that that was with minimal output, so there could still be issues.