# Pure C recursive solution, 4ms, beats 100%.

• ``````void qs(int *nums, int len) {
if (len < 2) return;
int key = nums[len - 1];
int i;
for (i = 0; i < len - 1 && nums[i] > key; i++);
if (i == len - 1) {
qs(nums, len - 1);
return;
}
int j;
for (j = i + 1; j < len - 1; j++) {
if (nums[j] > key) {
int tmp = nums[j];
nums[j] = nums[i];
nums[i++] = tmp;
}
}
nums[len - 1] = nums[i];
nums[i] = key;
qs(nums, i);
qs(nums + i + 1, len - i - 1);
}

void helper(int *coins, int len, int amount, int cur, int *min) {
if (len < 1) return;
int n = amount / coins[0]; //coins[0] is the biggest coin.
//at first, eat as much as possible.
amount -= n * coins[0];
cur += n; //current coins number.
if (!amount) { //one possible solution.
*min = *min < cur ? *min : cur;
return;
}
//coins[0] is the biggest coin and we already eat as much as we can,
//so if the number of current coins are still bigger than *min, no more operations needed.
if (cur >= *min) return;
int i;
for (i = 0; i <= n; i++) {
helper(coins + 1, len - 1, amount, cur - i, min);
amount += coins[0];
}
}

int coinChange(int* coins, int coinsSize, int amount) {
// desc sort.
qs(coins, coinsSize);
int min = INT_MAX;
helper(coins, coinsSize, amount, 0, &min);
return min == INT_MAX ? -1 : min;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.