COIN SUM INFINITE

1

I have understood the approach but I cannot seem to figure out why my code is not working as expected.

int Solution::coinchange2(vector<int> &A, int B) {
    vector<int> dp(B+1, 0);
    sort(A.begin(), A.end());
    dp[0]=1;
    for(int i=1; i<=B; i++){
        for(int j=0; j<A.size(); j++){
            if(i-A[j]>=0)
                dp[i]= (dp[i] + dp[i-A[j]])%1000007;
        }
    }
    // for(int i=0; i<=B;i++)
    //     cout <<dp[i]<<" ";
    return dp[B];
}
2

Change the looping order, Since you have to process each coin one by one for all “i” before going for the next coin.

correct way is below.

int Solution::coinchange2(vector<int> &A, int B) {
    vector<int> dp(B+1, 0);
    dp[0] = 1;
    int mod = 1000007;
    for(int j=0; j<A.size(); j++){
        for(int i=A[j]; i<=B; i++){
            dp[i] = (dp[i] + dp[i-A[j]])%mod;
        }
    }
    return dp[B];
}
3

Can you please explain why the loop order matters?
I am unable to understand

4

Because in this solution there is overlap, so for example
[1,2,3] s = 4
4 would be 1 + 1 + 2 would repeat twice