【回溯-数字全排列&&dfs】LCR 135. 报数

实现一个十进制数字报数程序，请按照数字从小到大的顺序返回一个整数数列，该数列从数字 1 开始，到最大的正整数 cnt 位数字结束。

示例 1：

输入：cnt = 2
输出：[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99]

cnt位数字的全排列，每个位取值范围【0-9】，故一共 Math.pow(10,cnt)个数字，由于从1开始所以要去掉0.

使用回溯依次从左向右设置数字，第i位数字取值【0，9】一直到设置到第cnt位，完成。

代码：

     static class Solution{
        public int k=0;
        public int[] countNumbers(int cnt) {
            int[] ans=new int[(int)Math.pow(10,cnt)-1];
            dfs(0,cnt,0,ans);
            return ans;
        }

        public void dfs(int i,int cnt,int v,int[] ans){
            if(i==cnt){
                if(v>0) ans[k++]=v; //不含1
                return;
            }

            for(int d=0;d<=9;d++){
                dfs(i+1,cnt,v*10+d,ans);
            }
        }
    }