Question: I am currently working through H-99 Questions after reading Learn You a Haskell. So far I felt like I had a pretty good grasp of the concepts, and I didn't have too much trouble solving or understanding the previous problems. However, this one stumped me and I don't understand the solution.

**The problem is:**

Generate the combinations of K distinct objects chosen from the N elements of a list

In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.

**The solution provided:**

```
import Data.List    

combinations :: Int -> [a] -> [[a]]
combinations 0 _  = [ [] ]
combinations n xs = [ y:ys | y:xs' <- tails xs, ys <- combinations (n-1) xs']

```

The main point of confusion for me is the y variable. according to how tails works it should be getting assigned the entire list at the beginning and then that list will be preppend to ys after it is generate. However, when the function run it return a list of lists no longer than the n value passed in. Could someone please help me understand exactly how this works?

Answer: 
Variable `y` is not bound to the whole `xs` list. For instance, assume `xs=[1,2,3]`. Then:

```
y:xs' is matched against [1,2,3]  ==> y=1 , xs'=[2,3]
y:xs' is matched against [2,3]    ==> y=2 , xs'=[3]
y:xs' is matched against [3]      ==> y=3 , xs'=[]
y:xs' is matched against []       ==> pattern match failure

```

Note that `y` is an integer above, while `xs'` is a list of integers.

---

The Haskell code can be read a a non-deterministic algorithm, as follows. To generate a combination of `n` elements from `xs`, get any tail of `xs` (i.e., drop any number of elements from the beginning). If the tail is empty, ignore it. Otherwise, let the tail be `y:xs'`, where `y` is the first element of the tail and `xs'` the remaining (possibly empty) part. Take `y` and add it to the combination we are generating (as the first element). Then recursively choose other `n-1` arguments from the `xs'` remaining part, and add those to the combination as well. When `n` drops to zero, we know there is only one combination, namely the empty combination `[]`, so take that.
`y` is not appended to `ys`. That would involve the `(++) :: [a] -> [a] -> [a]` operator.

For that matter the types would not match if you tried to append `y` and `ys`. `y` has type `a`, while `ys` has type `[a]`.

Rather, `y` is consed to `ys` using `(:) :: a -> [a] -> [a]` (the cons operator).

The length of the returned list is equal to `n` because `combinations` recurses from `n` to `0` so it will produce exactly `n` inner lists.