< Back





967. Numbers With Same Consecutive Differences

We're asked to find all combinations of numbers with length n where each consecutive number has a
difference of k.

Another backtracking problem, think of the combinations as nodes on a graph. We're essentially
conducting DFS, starting from a node like [1,0,0] and providing the next index to start searching
from the subsequent calls to backtrack().

At each step in the search, we're checking our neighbor nodes from range 0 - 9 to see if the
difference between the current node and the next node have an absolute value of k. If so, we visit
the next node.

If the size of our combination reaches n, we append it to the answer list. Eventually we traverse
all paths of our graphs and find all combinations that satisfy our constraints.

The solution is as follows:


  class Solution:
      def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
          s, ans = [0] * n, []

          def backtrack(t: List[int], j: int) -> None:
              if j == n:
                  ans.append(int("".join(map(str, t))))
                  return

              for l in range(10):
                  if abs(t[j - 1] - l) == k:
                      t[j] = l
                      backtrack(t, j + 1)

          for i in range(1, 10):
              s[0] = i
              backtrack(s, 1)

          return ans


_ Time Complexity:

  O(2^n) - Where n is the desired length of the combinations.

_ Space Complexity:

  O(2^n) - The size of the recursion stack.