Hey @bansal1232, you are right, the worst case runtime is theoretically \mathcal{O}(n^2), but a clever optimization and the constraints make it fast enough to pass the time limit.

The standard coin change dp algorithm would be something like

for(int i=1; i<=N; ++i){
int val = A[i];
for(int j = 0; j + val < MAX; ++j) if(is[j]) is[j + val] = 1;
}

See the last section on this page.

As you can see there are 2 differences. The first is `"sort(A+1, A+1+N);"`

. The second is `"if(is[val]) continue;"`

. What do these do together?

The sorting makes sure that the smaller coins are handled first and all values you can make with smaller coins are marked 1. Now it is possible that a larger coin can be made with some combination of smaller coins. Hence this larger coin is *effectively redundant*. Every sum that can be made using this coin can also be made using some combination of smaller coins. So the values at those sums will already be marked 1 and we do not need to think further about it. Now since the constraints specify that the value of each coin will be within 200000 (which is quite low), this occurs very frequently. We can detect this because `is[val]`

will be marked 1 for that coin. And whenever this happens the inner loop is skipped, hence it is fast enough to pass the time limit.

Hope the explanation is clear. On a personal note, I cursed myself after the contest because I hadn’t thought of this trick