TopCoder problem "NumberPartition" used in TCHS SRM 54 (Division I Level Three)



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

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9750

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13523&pm=9750

Writer:

mateuszek

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Dynamic Programming, Math, Search