backtracking
As the problem says, you should print all possible partitions of S into t co-prime numbers.
The order doesn't matter, so If you have to choose 1 & 2 & 5, you just need to print 1 2 5 not 5 2 1 or 2 5 1. This fact prunes backtracking and helped me pass time limit.
I implemented a function called solve( start, m, d ). In this function I start checking from start, and each time I find a number that is coprime to the selected items, I put it in the list and keep on backtracking with ( number, m-number, d+1 ), when the function reaches at ( d == numberOfPartitions ) and m is equal to zero( that means there are no values to choose and the partitioning is complete ), I completely print the selected list.
No comments:
Post a Comment