Prologのsubsetですが、リストと再帰を組合せた表現は強力です。

subset([],[]).
subset([A|B],[A|C]) :-
  subset(B,C).
subset([A|B],C) :-
  subset(B,C).

?- subset([1,2,3],X).
X = [1, 2, 3] ;
X = [1, 2] ;
X = [1, 3] ;
X = [1] ;
X = [2, 3] ;
X = [2] ;
X = [3] ;
X = [].

?-