OI-Wiki-DFS-正整数的分解

解题思路

把正整数num分为m个整数，如6 = 1 + 2 + 3，排在后面的数必须大于等于前面的数，输出所有方案。

解题思路

需要用dfs算法。dfs的模板为：

void dfs()//参数用来表示状态
{
    if(到达终止状态)//递归出口
    {
        ...//根据题意来添加
        return；
    }
    if(越界或者不合法状态)
        return;
    else
    {
        for(扩展方式)
        {
            if(扩展方式所达到的合法状态)
            {
                ...//根据题意来添加
                vis[i]=1;//标记
                修改（剪枝）
                dfs();
                vis[i]=0;
                //是否还原标记根据题意来
                //如果加上还原标记，就是回溯算法
            }
        }
    }
}

解题代码

class Solution:
    def Divide(self, num: int, m: int) -> list[int]:
        result = []
        arr = [0 for _ in range(m)]

        # 递归的任务：每次递归从还能选的因子[last, remind]里面选一个，达到level以后看看是不是可以加进结果，然后返回
        def dfs(remind: int, level: int, last: int):
            if level >= m:  # dfs到了最大层级，该返回了
                if remind == 0:  # arr里面的所有因子加起来为num
                    result.append(arr[:m])
                return
            if remind >= last:  # last是上次遍历时候的因子，下一个level取的因子
                for i in range(last, remind + 1):
                    arr[level] = i
                    dfs(remind - i, level + 1, i + 1)  # 找下一个比这次因子大的因子，一直到恰好找到或者remind太小以至于没法找到
        dfs(num, 0, 1)
        return result