Numbers With Same Consecutive Differences

 Numbers With Same Consecutive Differences

Return all non-negative integers of length N such that the absolute difference between every two consecutive digits is K.

Note that every number in the answer must not have leading zeros except for the number 0 itself. For example, 01 has one leading zero and is invalid, but 0 is valid.

You may return the answer in any order.

 

Example 1:

Input: N = 3, K = 7
Output: [181,292,707,818,929]
Explanation: Note that 070 is not a valid number, because it has leading zeroes.

Example 2:

Input: N = 2, K = 1
Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

 

Note:

1. 1 <= N <= 9
2. 0 <= K <= 9

class Solution {

public:

   

    vector<int> numsSameConsecDiff(int N, int K){

     vector<int> ans;

        if (N == 1) ans.push_back(0);

        for (int i = 1; i <= 9; i++)

            dfs(N - 1, K, i, ans);

        return ans;

    }

private:

    void dfs(int N, int K, int cur, vector<int>& ans) {

        if (N == 0) {

            ans.push_back(cur);

            return;

        }

        int last = cur % 10;

        if (last + K <= 9)

            dfs(N - 1, K, cur * 10 + (last + K), ans);

        if (last - K >= 0 && K != 0)

            dfs(N - 1, K, cur * 10 + (last - K), ans);

    }

};

-------------------------------------------------------------------------------------

class Solution {

public:

   

    vector<int> numsSameConsecDiff(int N, int K){

//         vector<int> v,res;

//         int i=1;

//           if(K<6)

//            {

//                 while(i<10){ 

//                     v.push_back(i);

//                     ++i;

//                 }

//            }

//             else

//             {

//                 v.push_back(1);

//                 v.push_back(K);

//                 i=1;

//                 if(i+K<10)

//                 v.push_back(i+K);

//                 ++i;

//                 while(i+K<10)

//                {

//                v.push_back(i));

//                v.push_back(i+K);

//                     ++i;

//                }

//             }

     

//         for(int i=0;i<N-1;++i)

//         {

//             int n=v.size();

//             for(int j=0;j<n;++j)

//             {

                

//                 int x=v[j]%10;

               

//                 if(x-K>=0)

//                     res.push_back(v[j]*10+(x-K));

//                 if(x+K<10)

//                      res.push_back(v[j]*10+(x+K));

//             }

//             v.clear();

//             sort(res.begin(),res.end());

//             auto ip=unique(res.begin(),res.end());

//             res.resize(distance(res.begin(),ip));

//             v=res;

            

//             res.clear();

//         }

//         vector<int> ans;

//         if(N==1)

//         {

//             return {0,1,2,3,4,5,6,7,8,9};

//         }

        

//        

//         if(N==1)

//             ans.push_back(0);

//         return ans;

        

//     }

    };