This is Perl, but the algorithm is straightforward and should be easy to implement in any language:
#!/usr/bin/perl
sub part {
my ($n, $b, $min) = @_;
$min = 0 unless defined $min;
# base case
if ($b == 0) {
if ($n == 0) { return ( [] ) }
else { return () }
}
my @partitions;
for my $first ($min .. $n) {
my @sub_partitions = part($n - $first, $b-1, $first);
for my $sp (@sub_partitions) {
push @partitions, [$first, @$sp];
}
}
return @partitions;
}
The function part gets two arguments: $n$ is the total number of beans that you want (5 in your example) and $b$ is the number of buckets (3 in your example). It also gets an auxiliary argument, $min$, which is the smallest permissible bucket value. This defaults to 0 if it is not supplied.
The function is recursive, just as you suggested. The base case is no buckets, $b=0$. If there are no beans to put into the buckets ($n=0$ also) then this can be satisfied in exactly one way, by an empty array of buckets []. Otherwise there is no solution because there are beans left over but no buckets to put them in.
If $b>0$ then the function will accumulate a list of possible partitions of $n$ beans into $b$ buckets in the array @partitions. It will do this by selecting the number of beans to go into the first bucket ($first$), recursively allocating the remaining beans into $b-1$ buckets, and assembling the two into a complete solution, which it will append to @partitions. This is just what you suggested in your question.
The number of the beans in the first bucket must be at least $min$, and at most $n$, the total number of beans.
The function then calls itself recursively: there are $n-first$ beans to allocate to $b-1$ buckets, but no bucket can have fewer than $first$ beans. This last bit is the only tricky part: it ensures that the number of beans never decreases from each bucket to the next, and so that each generated partition is unique. (Without this restriction, [1,2,2], [2,1,2], and [2,2,1] would be different solutions. With this restriction, only [1,2,2] is generated.)
The recursive call returns a number of partitions of $n-first$ beans into $b-1$ buckets. $first$ is appended to each of these (that's [$first, @$sp], which makes a single array out of $first and the contents of $sp) and the resulting partitions of $n$ beans into $b$ buckets are pushed onto @partitions. When this has been done for each permissible value of $first$, the complete @partitions list is returned.
To test your example, I did:
for my $p ( part(5, 3) ) {
print "@$p\n";
}
Which printed:
0 0 5
0 1 4
0 2 3
1 1 3
1 2 2
To get the partitions with largest element first, just change [$first, @$sp] to [@$sp, $first].
Some minor optimization are possible. For example, if $n < b\cdot min$ then one can halt the recursion immediately, returning no solutions.
Best Answer
Consider the subproblem of determine if the array has $(i, j)$ such that $0 \le (T[i] + T[j] - k) \le 2$; that is, $k \le T[i] + T[j] \le 2 + k$. Look at the following table for an example algorithm with input $\{a, b, c, d\}$:
$$\begin{array} {c|cccc} & 0 & 1 & 2 & 3 \\ \hline 0 & a + a & a + b & a + c & a + d \\ \hline 1 & b + a & b + b & a + c & b + d \\ \hline 2 & c + a & c + b & a + c & c + d \\ \hline 3 & d + a & d + b & a + c & d + d \\ \hline \end{array}$$
If that table were a height map, it would slope up from the bottom left to the top right.
So for any given column, you should be able to find the first row $s$ at least as large as $k$ and the last row $t$ no larger than $2 + k$. If $s \le t$ then you found a solution. If not, find the $s,t$ of the next row. Note that you can use the $s,t$ of the previous row to make the search faster.