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.