For a subset $$$A \subset {1, \ldots, n}$$$ we introduce the notation

for convenience. First, note that $$$\mathcal{I}$$$ always contains $$$\varnothing,$$$ since $$$s(\varnothing) = 0$$$. As a result we cannot violate condition $$$1.$$$ Similarly, it is impossible to violate condition $$$2,$$$ since for $$$A \supset B$$$ we have

and $$$s(A \setminus B) \geq 0$$$ by non-negativity of the weights $$$w_i.$$$

We say a set $$$A$$$ is constrained if $$$s(A) \leq c$$$ and for all $$$x \not \in A,$$$ $$$s(A \cup {x}) \geq c.$$$ Clearly if we can find constrained sets $$$A, B$$$ with $$$|A| \neq |B|$$$ then we have a contradiction to the third condition.

Consider the sets $$$M_{\min}$$$ and $$$M_{\max}$$$ constructed as follows:

For $$$M_{\min},$$$ iterate through the indices $$${1,\ldots, n}$$$ in non-decreasing order of $$$w_i.$$$ At each index, if adding it to the set keeps $$$s(M_{\min})$$$ at most $$$c,$$$ then add it to $$$M_{\min}.$$$ For $$$M_{\max},$$$ perform the same algorithm with the indices initially in non-increasing order of weights.

It is well known that $$$M_{\min}$$$ is the constrained set with the maximum size and $$$M_{\max}$$$ is the constrained set of minimum size. The proof is quite simple and thus is left as an exercise.

If $$$|M_{\min}| \gt |M_{\max}|$$$ then we are done. Otherwise, we know that all constrained sets have the same size; call this $$$k.$$$

We now make the following claim: If $$$|A| \gt |B|$$$ are sets which contradict property $$$3$$$, then there exist sets $$$C \supset A$$$ and $$$D \supset B$$$ such that $$$|C| = k$$$ and $$$|D| = k - 1$$$ which also contradict this property. We split the proof of this claim into two lemmas.

Lemma 1. If $$$|A| \lt k$$$ then we can construct $$$|C| = k.$$$

Proof: Since $$$|B| \lt |A| \lt k$$$ neither of these sets are constrained. Then there exist indices $$$i,j$$$ which can be added to $$$B$$$ and $$$A$$$ respectively. We can add $$$x = \text{argmin}_{u \in {i,j}} w_u$$$ to both sets. The proof is completed by induction.

Lemma 2. If $$$|A| - |B| \gt 1$$$ then we can construct $$$|C| - |D| = 1.$$$

Proof: Since $$$|B| \lt k - 1$$$ there exists some element which can be added to $$$B.$$$ If this element is not in $$$A$$$ then it does not affect the validity of our contradiction. If it is in $$$A,$$$ then our pair $$$A,B$$$ is not valid by definition of property $$$3$$$.

Finally, note that two sets $$$A,B$$$ form a valid pair if and only if the minimum weight of an index in $$$A \setminus B$$$ cannot be added to $$$B.$$$ In fact, if a pair $$$A,B$$$ contradicts property $$$3,$$$ then there exists a pair $$$C,D$$$ which also contradicts the property, such that the minimum weight element in $$$C$$$ does not occur in $$$D.$$$ The proof of this claim is very similar to that of the lemmas above, and the reader is encouraged to work out the details.

So now what we are looking for is a pair of sets $$$A,B$$$, such that the minimum element of $$$A$$$ is large enough that we cannot add it to $$$B$$$. What we will do is construct the sets $$$A,B$$$ with the greatest minimum and smallest allowable final element, respectively, since if a pair $$$A,B$$$ exists then this pair is also valid.

The first set can be constructed by iterating over suffixes of the weights in sorted order and taking $$$M_{\min}$$$ of the shortest suffix which satisfies $$$M_{\min} = k.$$$ The second set is simply $$$M_{\max} \setminus {u},$$$ where $$$u$$$ is the element of minimum weight. We can construct these sets and check if they form a valid contradiction. If they do not, then the set of solutions is a matroid.