题意整理：

题目给出数字n和m，要求计算所有的长度为n的数中，各个位上的数字之和为m的这些数的和的值。 题目中的各个位指的是十进制位，既数字 123 的各个位上数字的和为$1+2+3=61+2+3=6$1+2+3=6

方法一：枚举数字计算

核心思想：

本题n最大为6，所以可以枚举所有可能的数字进行判断即可

核心代码：

class Solution {
public:
    long long sum(int n, int m) {
        long long ans = 0;
        int begin = 1, end = 1;
        while(--n) {
            //计算起始数字
            begin *= 10;
        }
        end = begin * 10 - 1;//结束数字
        for(int i = begin; i <= end; ++i) {
            //枚举每一个长度为n的数字
            int p = i, cnt = 0;
            while(p) {
                cnt += p % 10;
                p /= 10;
            }
            if(cnt == m) ans += i;//符合条件
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：$O(n\ast 10^n)O(n*10^n)$O(n∗10n)。既对所有可能的数字进行枚举的代价为$O\left(10^n\right)O(10^n)$O(10n)，每个数字枚举n位

空间复杂度：$O\left(1\right)O(1)$O(1),只使用了常数个变量

方法二：递归与剪枝

核心思想：

方法一的枚举做了很多无用的计算，例如对于$n=3,m=3n=3,m=3$n=3,m=3，对于$120-199，300-999120-199，300-999$120−199，300−999等区间内的数字明显是不可能符合条件的，无需计算。可以通过递归剪枝的方式减少这些计算，当发现不可能满足要求时，不再递归。既方法一是对满十叉树进行计算，而方法二省去了很大枝叶开销 下面是对$n=3,m=3n=3,m=3$n=3,m=3剪枝后的递归树，可以发现比三层的满十叉树少了很多节点

核心代码：

class Solution {
public:
    long long ans = 0;
    void dfs(int n, int m, int num) {
        if(n == 0) {
            //递归结束，判断是合法
            ans += m == 0 ? num : 0;
            return;
        }
        //剩余数字都为0仍太大，或全为9仍太小，剪枝
        if(m < 0 ||  n * 9 < m) return;
        n -= 1;
        num *= 10;
        for(int i = 0; i <= 9; ++i) {
            if(num + i > 0) {
                //不允许0为前缀
                dfs(n, m - i, num + i);
            }
        }
    }
    long long sum(int n, int m) {
        dfs(n, m, 0);
        return ans;
    }
};

复杂度分析：

时间复杂度：$O\left(10^n\right)O(10^n)$O(10n)。递归深度最多为n,每次最多对该位10个数字递归

空间复杂度：$O\left(n\right)O(n)$O(n),既递归使用的栈深