There was this question in one of my class notes with a solution, where John has 2 of each coin with values based on 2 raised to the power of n and we have to help him calculate the number of different ways that can represent sum with the coins he has. The solution provided wasn’t finding the combinations at all and finding the answer in some mathematical way, and I’m struggling to understand how it calculates the number of ways to represent a target value (sum) with these coins. So for example, with a given input value sum = 6, the algorithm must return 3. The following three representations are possible for John in this case:
{1, 1, 2, 2}, {1, 1, 4} and {2, 4}. You may assume that sum will be between 1 and 1,000,000,000,000,000,000 inclusive.

Here is the solution:

public static long Solve(long sum)
{
if (sum < 0) return 0; // No coins and no sum possible
if (sum is 0) return 1; // Complete combination found

            if(!_cache.ContainsKey(sum))
            {
                if (sum % 2 is 0)
                {
                    _cache.Add(sum, Solve(sum / 2) + Solve(sum / 2 - 1));
                }
                else
                {
                    _cache.Add(sum, Solve((sum - 1) / 2));
                }
            } 
            return Convert.ToInt64(_cache[sum]);           
        }

I know that it’s using dynamic programming to store the possible combinations and I understand that part but what I don’t understand is how it’s making sure it’ll get all the possible combinations with 2 of each coin? What the significance of checking even and odd is? Why it doesn’t need to add the results if it’s odd but needs to for even numbers? I saw this postBinary Representation and it has an explanation about like bitwise operations which I thought was how this was working through, but I can’t see how it’s doing that either.

Also these 2 lines are the core of what I don’t understand and why it’s doing sum/2 instead of something like Floor(log(sum)) to get the closest power of 2 value.

_cache.Add(sum, Solve(sum / 2) + Solve(sum / 2 - 1));

_cache.Add(sum, Solve((sum - 1) / 2));

I would greatly appreciate it if someone could break down the logic of this code and how this algorithm arrives at the number of combinations?