sub funcP {
    return [], rec(@_);
}

sub rec {
    return () unless @_;
    map {
        my $first = shift;
        [$first], map { [ $first, @$_ ] } rec(@_)
    } @_;
}

my @result = grep{ @$_ == 3 } funcP( @menge );

use strict;
use warnings;
use Data::Dumper;

print Dumper(kTeilmengen([1..6], 3));

sub kTeilmengen {
    my ($Menge, $k) = @_;
    my $n = @$Menge;
    return [$Menge] if $n <= $k;    # eigentlich $n == $k
    return [[]] if $k <= 0;    # eigentlich $k == 0
    my $e = shift @$Menge;
    [
        (map { [$e, @$_] } @{kTeilmengen([@$Menge], $k-1)}),
        @{kTeilmengen([@$Menge], $k)}
    ];
}