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=5In
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;
}