Minimize sum of squared error
You are looking for an optimal 1-dimensional k-means algorithm.  The k-means objective function for partitioning the data $x_1, \ldots, x_n$ into $k$ sets $S = \{S_1, \ldots, S_k\}$.

$$
\sum\limits_{i=1}^k \sum\limits_{x \in S_i}\lVert x - \mu_i \rVert^2
$$

where $\mu_i$ is the mean of $S_i$ [1].

You can apply a dynamic programming algorithm to the problem [2].


Let the data $x_1, \ldots, x_n$ be sorted in non-decreasing order.
Fill a $(n + 1) \times (k + 1)$ array, $D$, with the minimum sum of squared errors, for the first $i$ entries, using $m$ clusters.  This can be calculated as

$$
   D[i,m] := \min\limits_{m \le j \le i} \left\{ D[j-1,m-1] + d(x_j, \ldots, x_i) \right\}
   $$

where $d(x_j, \ldots, x_i)$ is the sum of squared errors from their mean.  For $1 \le i \le n$ and $1 \le m \le k$, and the base cases are $d[i,m] = 0$ if $i=0$ or $m=0$.

Thus, the entry $D[n,k]$ contains the optimal sum of squared errors for the original problem, now all that is left to do is to extract the answer.

Note that $d(x_j, \ldots, x_i)$ can be computed iteratively to speed up the algorithm, as

$$\begin{align*}
   d(x_j, \ldots, x_i) &amp;= d(x_j, \ldots, x_{i-1}) + \frac{i-1}{i} (x_i - \mu_{i-1})^2 \\
   \mu_i &amp;= \frac{x_i + (i - 1) \mu_{i-1}}{i}\end{align*}
   $$

Thus, $D$ can be computed in $O\left(n^2k\right)$ time, since there are $nk$ entries, and each takes $O(n)$ time to compute.
Now, we fill a $n \times k$ array, $B$, whose entries, $B[i,m]$, contain the index of the smallest (first) element in the cluster that contains entry $i$, which can be calculated as

$$
   B[i,m] := \arg\min\limits_{m \le j \le i} \left\{ D[j-1,m-1] + d(x_j, \ldots, x_i) \right\}
   $$

for $1 \le i \le n$ and $1 \le m \le k$.  This takes $O\left(n^2k\right)$ time.

Thus, we can backtrack from $B[n,k]$ to find the clustering.  The clusters are defined recursively as

$$\begin{align*}
   S_k &amp;= \{B[n,k], \ldots, x_n\} \\
   S_i &amp;= \{B[x_j,k], \ldots, x_j \mid x_{j+1} := \min S_{i+1}\}
   \end{align*}$$

The backtracking takes $O(k)$ time.


The algorithm runs in $O\left(n^2k\right)$ time, and requires $O(nk)$ space.

[1] http://en.wikipedia.org/wiki/K-means_clustering

[2] http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf