NumberPartition | Topcoder Archive

Problem Statement

A partition of the number n is the set of numbers that all sum up to n. For example, we have 5 different partitions of 4: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}, {4}. If we sort all the numbers within each set, we can treat each partition as a sorted list of numbers and so introduce a lexicographic order on all partitions. For example, the partitions of 4 mentioned before are given in order. You are given ints n and k. Determine all the partitions of n, sort them in lexicographical order, and return a int[] containing the k-th one (k is a 1-based index). If there are not enough partitions of n, return an empty int[].

Definition

Class:: NumberPartition
Method:: kthPartition
Parameters:: int, int
Returns:: int[]
Method signature:: int[] kthPartition(int n, int k)
(be sure your method is public)

Notes

The lexicographical order is exactly the same as in a dictionary. A int[] A is lexicographically before a int[] B if there exists an integer i such that A[i] < B[i] and A[j] = B[j] for all j < i or if A is a proper prefix of B.

Constraints

n will be between 1 and 50, inclusive.
k will be between 1 and 1000000, inclusive.

Examples

```
4
```
```
1
```
```
Returns: {1, 1, 1, 1 }
```
Example from the problem statement.
```
4
```
```
3
```
```
Returns: {1, 3 }
```
```
17
```
```
123
```
```
Returns: {1, 1, 1, 3, 3, 3, 5 }
```
```
12
```
```
1234
```
```
Returns: { }
```
There are less then 1234 partitions of 12.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.