Not the exercise. This lists every string of a given length made from H and T, the outcomes of tossing a coin n times. Each call returns a list, and the caller builds a longer list from it.
def tosses(n):
if n == 0:
return [""] # one outcome: nothing tossed
shorter = tosses(n - 1)
return ["H" + s for s in shorter] + ["T" + s for s in shorter]
print(tosses(2)) # -> ['HH', 'HT', 'TH', 'TT']
- The base case is a list with one answer in it
tosses(0) is [""], not []. There is exactly one way to toss a coin zero times; an empty list would say there are none, and everything built on it would be empty too.
- One call, used twice
shorter is worked out once and reused for both H and T. Calling tosses(n - 1) twice would give the same answer at twice the cost, and the waste doubles at every level.
- New strings, never edited ones
"H" + s makes a new string. With lists you have to be as careful: adding to a list you got back would change it everywhere it is shared.
Split the list into its first item and the rest. Every subset of the whole list either leaves the first item out, and is a subset of the rest, or puts it in front of a subset of the rest.
Base case: an empty list has exactly one subset, [[]]. Otherwise work out without = subsets(items[1:]) once.
Return without + [[items[0]] + s for s in without]. The second part builds new lists, so nothing in without is changed.
def subsets(items): if not items: return ____ without = subsets(items[____:]) return without + [[items[0]] + s for s in ____]
def subsets(items):
if not items:
return [[]]
without = subsets(items[1:])
return without + [[items[0]] + s for s in without]
The empty list has one subset. Return [] and there is nothing for the next level to build on, so every answer comes back empty.
Writing s.insert(0, items[0]) instead would change the lists inside without, which is also the first half of the answer, so both halves would end up with the item in them.
Each level returns twice as many subsets as the one below it. Ten items give 1,024 subsets, twenty give over a million. That is the size of the question, not a flaw in the code.
itertools.combinations(items, k) gives the subsets of one size lazily, and chaining it over every k gives them all without building a million lists at once. Use it in real code; write this to see how the choices are built.
- Return only the subsets whose values add up to a target.
- Produce the subsets lazily with yield, so twenty items do not build a million lists at once.
- Allow repeated values and make sure each different subset appears once.