Proof that sorting + greedy works
The coding part is straightforward from the hints. However, it is the proof that sorting + greedy works the interviewer would be asking.\n1. If coins[:i] has su
The coding part is straightforward from the hints. However, it is the proof that sorting + greedy works the interviewer would be asking.\n1. If `coins[:i]` has subset sums `0, 1, ..., x`, then for `coins[:i+1]` we can have these new sums by adding `v=coins[i]`: `v, v+1, ..., v+x`. If `v <= x+1`, then there is no gap between these two sequences, and thus we can have subset sums up to `v+x`. Note that this part does not require `coins` be to sorted.\n2.  If `coins[:i]` has subset sums `0, 1, ..., x`, and `coins[i] > x+1`, then the max subset sum for `coins[:i+1]` remains `x`. Proof by contradiction: suppose otherwise `coins[:i+1]` can have a subset of sum `x+1` (or greater), then this newly larger sum must be contributed by `coins[i]`, namely there exists a subset `S in range(i)` such that `sum([coins[j] for j in S]) + coins[i] = x + 1`. Since the values are all positive, we must the sum of subset `S` must be nonnegative, and thus `coins[i] <= x + 1`, a contradiction. Note that this part also does not require `coins` to be sorted.\n3.  Note that (1) & (2) only prove that `v+x` is *achievable* for `coins[:i+1]`; we yet to prove that it can not be larger than that. Again proof by contradiction: suppose `v=coins[i] <= x + 1`, and there exists a subset `S in range(i+1)` such that `sum([coins[j] for j in S]) = v+x+1`. Note that `i` is not necessarily in `S`.\n    3(a). If `i` is in `S`, then the sum of subset `S-{i}` is `x+1`, which contradicts that `coins[:i]` can only have consecutive subset sums up to `x`.\n\t3(b). If `i` is not in `S`, remove an arbitrary element `k` in `S` (doable because `S` is clearly not empty), denoted as `S2`. This time we need `coins[:i+1]` to be **sorted**: since `coins[i]>=coins[j]` for any j in `S`, we must have `sum([coins[j] for j in S2]) = (v-coins[k]) + x + 1 >= x + 1`, which contradicts that `coins[:i]` can only has consecutive sums up to `x`. \n\n```\nclass Solution:\n    def getMaximumConsecutive(self, coins: List[int]) -> int:\n        coins.sort()\n        x = 0\n        for v in coins:\n            if v <= x + 1:\n                x += v\n        return x + 1\n```
[]