dc
function should have the same parameter defination as the original problems
is a parameter defining the sacle of the problem. Different problem should be defined by different length of string s
def dc(self, s): # if catch the end if is_end(s): return hard_code_answer
# get answer of all branches
ans_list = []
for b in branch:
ans_list.append(self.dc(s - b))
# combine ans lists
ans = combine(ans_list)
return ans #, ans1, ans2 ... ```
def traverse(scope, cur, ans): if complete: ans.append(deep_copy(cur)) return
for step in step_candidates:
if possible(step):
cur.append(step)
self.traverse(scope - step, cur, ans)
cur.pop()
return ```
严格意义上这个算不上是DFS,而是BFS。这些题目的特征如下: