Stepping Number

Backtracking

A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a stepping number while 421 is not. A single digit integer, is always a stepping number. Given two integers low and high, return a sorted list of all the stepping numbers in the inclusive range [low, high].

Write a backtracking algorithm to solve this problem. The input contains 2 lines. The integer on the first line is low. The integer on the second line is high.

Constraint: 0 <= low <= high <= 2 * 109

Important Info:

• You must solve this problem using backtracking. If you do not use backtracking, then you will not get any points for this assignment.

Example 1:

Input:
0
15
Output:
0 1 2 3 4 5 6 7 8 9 10 12

Example 2:

Input:
300
350
Output:
321 323 343 345