Как придумать рекурсию?
Пусть каждое слово в масиве (4 элемента ?) - это позиция в 4-х позиционном двоичном числе 0 - есть слово, 1 нет слова. Итого, задача переформулируется так - сколько 4-х значных чисел можно сгенерировать, чтобы одна или более цифр числа была 0, исключая 0 (ответ 14 для 4-х значного, 0 и 15 не подходят )
Отобразить запись, типа 1001 в "яблоко апельсин" будет уже технической задачей...$words=['яблоко', 'банан', 'киви', 'апельсин'];
$min_words=1;
$max_words=3;

for($i=0;$i<2**count($words);$i++){
    $bin=str_pad(base_convert($i,10,2),count($words), "0", STR_PAD_LEFT);
    $numword=substr_count($bin,'1');
    if($numword<$min_words || $numword>$max_words) 
        continue;
    $result=[];               
    for($j=0;$j<strlen($bin);$j++){
        if($bin{$j}=='1') $result[]=$words[$j];
    }               
    echo '>',implode(' ', $result), "<br>\n";
}>апельсин
>киви
>киви апельсин
>банан
>банан апельсин
>банан киви
>банан киви апельсин
>яблоко
>яблоко апельсин
>яблоко киви
>яблоко киви апельсин
>яблоко банан
>яблоко банан апельсин
>яблоко банан киви
Можно так<?php

function find($arrS,$arrF){
    foreach($arrS as $sarr){
        $cnt = 0;
        foreach($sarr as $vs)
            if(in_array($vs,$arrF))
                $cnt++;
        if($cnt == count($arrF) && count($arrF) == count($sarr))
            return true;
                
    }
    return false;
}
function excerpt($arr,$maxDepth = 3,$arrSort = [] ,$valsPrev = [], $depth = 1){
    foreach($arr as $val){
        if(in_array($val,$valsPrev))
            continue;
        
        $varTmpArr = $valsPrev;
        array_push($varTmpArr,$val);
        
        if(!find($arrSort,$varTmpArr))
            array_push($arrSort,$varTmpArr);
        if($depth < $maxDepth)
            $arrSort = excerpt($arr,$maxDepth,$arrSort,$varTmpArr  , $depth +1);
    }  
    return $arrSort;
}

function convert($arr){
    
    $newArr = [];
    foreach($arr as $subarr){
        $newval = "";
        foreach($subarr as $val)
            $newval .= " ". $val;
        array_push($newArr,trim($newval));
    }
    return $newArr;
}

    
    foreach(convert(excerpt(['яблоко', 'банан', 'киви', 'апельсин'],3)) as $v)
        echo $v . "\n";
    ?>
Вывод
яблоко
яблоко банан
яблоко банан киви
яблоко банан апельсин
яблоко киви
яблоко киви апельсин
яблоко апельсин
банан
банан киви
банан киви апельсин
банан апельсин
киви
киви апельсин
апельсин