Introduction to Algorithms
Week 13: Exercises

1. Subsets

Write a function subsets() that takes an integer N ≥ 0 and returns a list of all subsets of {1, 2, …, N}. For example:

>>> subsets(3)
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

2. Combinations

Write a function combinations() that takes a list l and an integer k, and returns a sequence of all combinations of k elements of l. For example:

for x in combinations([2, 4, 6, 8, 10], 3):
   print(x)

[2, 4, 6]
[2, 4, 8]
[2, 4, 10]
[2, 6, 8]
[2, 6, 10]
[2, 8, 10]
[4, 6, 8]
[4, 6, 10]
[4, 8, 10]
[6, 8, 10]

Do not return a list of the combinations; instead, generate them as needed.

3. Compositions

A composition of a positive integer N is a sequence of positive integers that add up to N. Order matters: if N = 4, then (1 + 3) and (3 + 1) are distinct compositions.

Write a function that takes an integer N and prints all its composiitons.