DFS要解决的问题类型1（判断有没有解）

要点

1. 这种类型的问题的dfs helper函数的一般是有返回值，并且返回值为boolean类型（true or false）

模版

Boolean dfs_helper(Node n, others) {    
    //1. Initial conditions
    //1.1. When to return True
    if (conditions) return true
    //1.2. When to return False
    if (conditions) return false

    Boolean existence = false

    //2. Backtracking
    for each child c of n {
        //2.1 Add conditions
        if (conditions): continue

        //2.2 Update states: change node value before backtracking if needed
        <update states>

        //2.3 backtracking
        if dfs_helper(Node c, others) succeeds:
            existence = true
        //2.4 Update states: change node value before backtracking if needed
        <update states>
    }

    //3. Return result
    return existence
}

DFS要解决的问题类型2（找到所有解）

要点

1. 这种类型的问题的dfs helper函数的一般是没有返回值
2. 在dfs helper函数传入list类型的参数来保存所有解的结果

模版

Boolean dfs_helper(Node n, single_result, result_list) {    
    //1. Initial conditions
    //1.1. No initial condition, result_list just appends single_result
    result_list.append(single_result)
    //1.2. result_list only appends single_result in some conditions
    if (conditions):
        result_list.append(single_result)

    //2. Backtracking
    for each child c of n {
        //2.1 Add conditions
        if (conditions): continue

        //2.2 Update states: change node value before backtracking if needed
        <update states>

        //2.3 backtracking
        dfs_helper(Node c, <Update single_result>, result_list)

        //2.4 Update states: change node value before backtracking if needed
        <update states>
    }
}