Given an array of denominations, how many combinations of coins to sum total cents

[zizz]

It doesn't seem to be working. I'm missing something somewhere....

I don't fancy working on someone else's code so I did my own implementation (according to the program development principle of Stepwise Refinement).

I think I came up with the same algorithm as you did:

1. Scan the number from the right and extract digits one by one.
2. Find the first digit that is smaller than the digit before. (note how the extracted digits appear in sorted order).
3. Then exchange this digit with the smallest bigger digit among the extracted digits. (note that this doesn't break the sorting)
4. Finally put the extracted digits back onto the number in reverse order.

The algorithm stops the first time it encounters a digit that is smaller than the previous digit. If digits appear with equal probability the expectation for this event is only a few couple of digits (2.22 if I got it right). In any case the complexity is dependent on the stochastic properties of the random sequence of digits and not the number of digits. That is the algorithm is O(1) rather than O(N).

int firstbigger(int N) {
	std::vector<int> v;
	v.push_back(0); // make room for one digit

	int d = N%10;
	int n = N/10;
	while (n > 0) { // extract digits from n from the right 
		v.push_back(d);
		int t = d;
		d = n%10;
		n = n/10;
		if (d < t) { // d is first digit smaller than previous digit
			for (int i=1; i<int(v.size()); ++i) {
				if (v[i] > d) { // first extracted digit bigger than d
					v[0] = v[i]; // swap in
					v[i] = d;
					for (int j : v) n = n*10 + j; // add digits back on n in reverse
					return n; // smallest bigger number
				}
			}
		}
	}
	return N; // no bigger number exists, or number is negative
}