题解 | #位数求和#

题意：
长度为n的数中，找到每位上的数字之和（例：256每位上的数字之和为2+5+6=13）为m的这些数的和，并求和。

方法一
暴力枚举

思路：因为n是位数且 ,n最大也就是999999，所以可以直接暴力枚举。
找到n位数的最小值与最大值区间，并在这个区间遍历，将每位上的数字之和等于m的值相加。

class Solution {
public:

    long long sum(int n, int m) {
        long long res=0;
        int min=pow(10,n-1),max=pow(10,n);//n位数的（最小值）和（最大值-1）
        for(int i=min;i<max;i++){//遍历
            int x=i,s=0;
            while(x){//求各个位上的数字之和
                s+=x%10;
                x/=10;
            }
            if(s==m)//比较，如果等于m，则加上zheg
                res+=i;
        }
        return res;

    }
};

时间复杂度：
空间复杂度：

方法二
dfs搜索+剪枝

思路：

递归，每一位都有0到9十种选择，最高位除外，只有1到9九种选择。
上述多叉树中，第0层是空串，第一层是最高位，可取1到9。之后的每一层都递归处理，可取0到9。
层数表示位数，例如：n位数，当到达第n层则可以判断该分支是否可取。
请在这里输入引用内容
剪枝：

if(m-i<0)//剪枝
    break;

因为m是每位上的数字之和，当 则说明该分支以下的子树不再满足条件，跳出循环。

class Solution {
public:

    long long res=0;
    int flag=0;//用于判断一个数不能含有前导0
    long long sum(int n, int m) {
        dfs(n,m,0);
        return res;

    }

    void dfs(int n,int m,int x){
        if(n==0){//凑齐n位数
            if(m==0)//如果x的各个位上的数字之和为m，则加上x
               res+=x; 
            return;
        }
        for(int i=0;i<10;i++){//每位数的范围是【0,9】
           if(flag==0&&i==0){//不能含有前导0,如果数的最高位是0，则跳过
               flag=1;
               continue;
           }
            if(m-i<0)//剪枝
                break;
            dfs(n-1,m-i,x*10+i);//n-1表示用掉一位，m-i表示减掉该位上的数，x表示形成的数
        }
    }
};

时间复杂度：
空间复杂度：