int getKth(int k, int* nums, int len)
{
	int result = nums[k];

	for(int i = k; i < len - 1; i++)
		nums[i] = nums[i + 1];

	return result;
}
char* getPermutation(int n, int k)
{
	if(n == 0) return NULL;

	char* result = malloc(sizeof(char) * (n + 1));
	int use;
	int nums[n];
	int fac[n];
	int len = n;

	fac[0] = 1;

	for(int i = 1; i < n; ++i) {
		nums[i - 1] = i;
		fac[i] = fac[i - 1] * i;
	}
	nums[n - 1] = n;

	for(int i = 0; i < n; ++i) {
		/* here k = n - 1, i.e. get 2th, index = 1 */
		use = getKth(((k - 1) / fac[n - 1 - i]), nums, len);
		len--;
		k -= ((k - 1) / fac[n - 1 - i]) * fac[n - 1 - i];
		result[i] = use + '0';
	}

	result[n] = '\0';

    return result;
}