Recursion
Loading
Loading
Recursion
Choose, explore, un-choose — and prune before you build something impossible.
By the end of this chapter
def subsets(nums): results = [] current = [] def explore(start): results.append(current[:]) # a COPY — current keeps mutating for i in range(start, len(nums)): current.append(nums[i]) # choose explore(i + 1) # explore current.pop() # un-choose explore(0) return resultsConcept
Without it you would have to copy the state at every node of the tree. Undoing the last decision lets a single buffer represent the current path, so the memory is O(depth) rather than O(nodes).
Generating every candidate and filtering at the end explores branches that were doomed from their second decision. If validity can be tested on a partial candidate, enforce it during construction.
def balanced_brackets(n): results = [] def build(current, opened, closed): if len(current) == 2 * n: results.append(current) return if opened < n: # legal to open build(current + "(", opened + 1, closed) if closed < opened: # legal to close ONLY while something is open build(current + ")", opened, closed + 1) build("", 0, 0) return resultsSign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 2 practice problems.