### 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

mateuszek

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming, Math, Search