Reference

https://en.wikipedia.org/wiki/Pascal's_rule

Because Pascals rule is so clean. I wanted a solution similar.

The idea is that when we get to the base case, we have either n == k or k == 0.

In the case that k == 0, there is only 1 way to select 0 items out of n numbers, which is an empty list.

In the case that n == k, there is only 1 way to select n items out of n numbers, which is to select them all.

As for the recursive case building. Pascals Rule tells us that the number of ways to select k items out of n items is equal to the number of ways to select k items out of (n-1) items plus the number of ways to select (k-1) items out of (n-1) items. So this means we just need to add the kth number to the set that didn't include it.

This isn't the fastest solution by any means.

```
public class Solution {
public List<List<Integer>> combine(int n, int k) {
// Pascal's Identity (n,k) = (n-1,k) + (n-1,k-1). All previous that don't include the new one, and all previous that do include.
List<List<Integer>> res = new ArrayList<>();
if (k == 0) {
res.add(new ArrayList<Integer>());
return res;
} else if (n == k) {
List<Integer> all = new ArrayList<>();
for (int i = 1; i <= n; i++) {
all.add(i);
}
res.add(all);
return res;
}
List<List<Integer>> prevWith = combine(n - 1, k);
List<List<Integer>> prevWithout = combine(n - 1, k - 1);
for (List<Integer> prev : prevWithout) {
prev.add(n);
}
res.addAll(prevWith);
res.addAll(prevWithout);
return res;
}
}
```