Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem

The following problem statement is given:
Let $S = \{s_1, s_2, \cdots, s_n\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s_i$ for every $i$ between $1$ and $n$. The goal is to find a subset of $S$ whose sum is maximum, subject to the constraint that the sum must be $\le K$.
Write an approximation algorithm which computes a sum which is at least half of the optimal solution on any given input. This algorithm must run in $O(n)$ time-complexity and $O(1)$ space-complexity.

I've been searching for some simple algorithm to satisfy these conditions and the closest I've come to is this, but since it makes use of sorting, the time-complexity is brought to $O(n\log n)$.

This is taken from a set of exercises given by my uni professor as preparation for the final exam. To be honest, I am not sure whether it is his original work or not, so I don't have any relevant reference to provide.

The idea is to set $K/2$ as the target.

• If there is any given number that is at least $K/2$, just return it.

• Otherwise, all given numbers are $

• Otherwise the sum of all given numbers is $>K$.

Let $prefix\_sum$ be $0$ initially. We will try adding all given numbers one by one to $prefix\_sum$ until it is $\ge K/2$, at which moment it cannot be $>K$ -- otherwise the last number added must be $>K/2$. Return it.

Here is an algorithm that implements the idea concisely. It runs in $O(n)$ time and $O(1)$ space.

• Let $prefix\_sum = 0$.

• For $i$ from $1$ to $n$:

• If $s_i\ge K/2$, return $s_i$. Else add $s_i$ to $prefix\_sum$.

• If $prefix\_sum\ge K/2$, return $prefix\_sum$.

• Return $prefix\_sum$.

StackExchange Computer Science Q#160138, answer score: 3