I read the solution here
http://www.algorithmist.com/index.php/Coin_Change
basically to find the number of ways to make change:
We are trying to count the number of distinct sets. it says
"
Since order does not matter, we will impose that our solutions (sets) are all sorted in non-decreasing order (Thus, we are looking at sorted-set solutions: collections).
For a particular N and S={S1,S2,...,Sm} (now with the restriction that S1<S2<...<Sm, our solutions can be constructed in non-decreasing order), the set of solutions for this problem, C(N,m), can be partitioned into two sets:
There are those sets that do not contain any Sm and
Those sets that contain at least 1 Sm
"
I don't have a strong mathematics background so I'm not sure how or why was that possible?
How did we figure out that the solution is the sum of the number of ways in which Sm isn't used plus the number of ways that we have at least one Sm
any reference will much be appreciated.
Best Answer
Let's say someone has worked out all the solutions. Let the solutions queue at two doors.
If a solution has an $S_m$, they go through the left door, otherwise they go through the right door.
The solutions that go through the left door all have an $S_m$ - at least one. The solutions that go through the right door have no $S_m$.
So the doors have split the set of all solutions into two subsets.
Count the two subsets. The two counts must add up to the full count of all solutions.