The backtracking algorithm CHOOSE is written using Cormens pseudocode notation. The parameters n, k, and e are nonnegative integers. The parameter s is a set of nonnegative integers. The algorithm prints a series of sets; each set is a subset of { 1, 2 ..., n }. The symbol is the empty set, and the symbol is set union.

CHOOSE(n, k, e, s) if k == 0 print(s) else for e = e to n CHOOSE(n, k 1, e + 1, s { e })

a.What sets will CHOOSE(4, 3, 1, ) print? Hint: enumerate the recursive calls breadth-first.

b.Let l and m be nonnegative integers. What does CHOOSE(l, m, 1, ) compute? Your answer must be one short sentence, stated in terms of l and m.