How to get all combinations of elements in an array with a size no less than and no more than K elements?

Question

PHP

There is a one-dimensional array of natural numbers sorted in ascending order, containing N elements. And a natural number K.
You need to create an algorithm (php script), it should produce a multidimensional array, which consists of arrays containing all combinations of elements of the input array and has a size of K. At the same time, each such array should remain sorted in ascending order.
Example:
Input array [1, 2, 3, 4]
K = 3
-
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

Answer 1

To train the brain, we tried to do this:

function process($input, $k, array $prefix = array())
{
    $result = [];

    if ( $k === 1 )
    {
        foreach ($input as $item)
        {
            $result[] = array_merge($prefix, [$item]);
        }
    }
    else
    {
        $n = count($input);
        $m = $n - $k + 1;

        for ( $i = 1; $i <= $m; $i++ )
        {
            $subInput = array_slice($input, $i, $k);
            $subPrefix = array_merge($prefix, [$input[$i-1]]);
            $r = process($subInput, $k-1, $subPrefix);
            $result = array_merge($result, $r);
        }
    }

    return $result;
}


$input = [1, 2, 3, 4, 5];
$k = 3;
$result = process($input, $k);
var_export($result);