Many of the recursion solutions use a helper function to write to a result set.
Is there a particular reason for this style, like time complexity, or to more easily analyze runtime with a recurrence relation?
I find it easier to wrap my head around a more traditional functional style for these problems.
For example, here are two solutions to “15.5 Generate the Power Set”, the first in the EPI style and the second in I think a more familiar recursive style. EPI style is O(n*2^n), I believe the alternate solution is also O(n^2 * 2^n), which may be the reason for the EPI approach.
from typing import List
def powerset(input_set: List[int]) -> List[List[int]]:
def compute_pset_marginal(idx: int, candidate_set: List[int]) -> None:
if idx == len(input_set):
powerset.append(candidate_set)
return
# compute candidate excluding current idx
compute_pset_marginal(idx + 1, candidate_set)
# compute candidate including current idx
compute_pset_marginal(idx + 1, candidate_set + [input_set[idx]])
powerset = []
compute_pset_marginal(0, [])
return powerset
def powerset_alt(input_set: List[int]) -> List[List[int]]:
if len(input_set) == 0:
return [[]]
suffix_pset = powerset_alt(input_set[1:])
return suffix_pset + [([input_set[0]] + l) for l in suffix_pset]
if __name__ == '__main__':
print(powerset([1,2,3]))
print(powerset_alt([1,2,3]))