` 1: 1+1+1+1+1`

` 2: 1+1+1+2`

` 3: 1+1+2+1`

` 4: 1+1+3`

` 5: 1+2+1+1`

` 6: 1+2+2`

` 7: 1+3+1`

` 8: 1+4`

` 9: 2+1+1+1`

` 10: 2+1+2`

` 11: 2+2+1`

` 12: 2+3`

` 13: 3+1+1`

` 14: 3+2`

` 15: 4+1`

` 16: 5`

The answer is obviously recursive, and the complexity is, of course O(2

^{n - 1}), exponential.

1: void doPartitions(int n, vector<int>* partition) {

2: if (n <= 0) { //the number cannot be partitioned further, so print

3: for (int i = 0; i < partition->size() - 1; i++)

4: cout << partition->at(i) << "+";

` 5: cout << partition->at(partition->size() - 1) << endl;`

6: return;

` 7: }`

8: int size = partition->size();

9: for (int i = 1; i <= n; i++) {

10: //add the current no to the partitions

11: //and generate partitions from the leftover number

` 12: partition->push_back(i);`

` 13: doPartitions(n - i, partition);`

14: while (partition->size() > size)

15: partition->pop_back(); //reset the partitions each iteration

` 16: }`

` 17: }`

What's left here is to find a way to print only the distinct solutions, but this is a simple exercise.

## No comments:

## Post a Comment