#967

Medium

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Numbers With Same Consecutive Differences

Generate all n-digit numbers where consecutive digits differ by k using efficient backtracking and BFS techniques.

Problem Statement

Given integers n and k, generate all integers of length n such that the absolute difference between every two consecutive digits is exactly k. Numbers cannot have leading zeros, meaning digits like '0' at the first position are invalid.

Return an array of all valid integers in any order. For example, for n = 3 and k = 7, the valid numbers are [181,292,707,818,929], excluding any number with leading zeros like 070. The solution should handle 2 <= n <= 9 and 0 <= k <= 9.

Examples

Example 1

Input: n = 3, k = 7

Output: [181,292,707,818,929]

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]

Example details omitted.

Constraints

2 <= n <= 9
0 <= k <= 9

Solution Approach

Recursive Backtracking with Pruning

Start from digits 1 through 9 and recursively append digits that satisfy the consecutive difference k. Immediately backtrack if the next digit is out of bounds or would introduce a leading zero, pruning invalid paths efficiently.

Breadth-First Number Construction

Use a queue to iteratively build numbers of length n, expanding each number by digits that maintain the consecutive difference k. This BFS approach ensures systematic level-by-level construction while avoiding recursion depth issues.

Combination of BFS and Backtracking for Optimization

Merge both approaches by starting BFS with single digits and applying backtracking when generating next candidates. This hybrid ensures pruning occurs early while still exploring all valid sequences efficiently.

Complexity Analysis

Metric	Value
Time	\mathcal{O}(2^{N})
Space	\mathcal{O}(2^{N})

Time complexity is O(2^N) because each digit can generate up to two candidates for the next position, leading to exponential growth. Space complexity is also O(2^N) to store the valid sequences in the result array and the recursion or BFS queue.

What Interviewers Usually Probe

Can you optimize by pruning paths that violate the consecutive difference constraint?
How would you systematically generate all numbers without recursion stack overflow?
Do you handle edge cases like n-digit numbers starting with zero or k = 0?

Common Pitfalls or Variants

Common pitfalls

Forgetting to disallow numbers with leading zeros, generating invalid numbers like 02 or 043.
Not pruning early, causing unnecessary exploration and exponential time wastage.
Misapplying the difference k, resulting in sequences where consecutive digits do not meet the required difference.

Follow-up variants

Find all numbers with consecutive differences forming an arithmetic sequence with variable differences per step.
Count the number of valid n-digit numbers without generating the actual numbers to optimize space.
Return numbers sorted in increasing order or with additional constraints like odd/even digit placement.

FAQ

What does 'Numbers With Same Consecutive Differences' require in terms of digit construction?

It requires generating all n-digit numbers where each consecutive pair of digits differs exactly by k, excluding leading zeros.

Can this problem be solved using iterative approaches instead of recursion?

Yes, BFS allows iterative number construction, systematically generating sequences without recursion and preventing stack overflow.

Why is pruning important in this problem?

Pruning prevents exploring sequences that cannot satisfy the consecutive difference, reducing exponential time and memory usage.

How do I handle the case where k = 0?

When k = 0, consecutive digits must be identical, so only repeated digits sequences are valid, still avoiding leading zeros.

What are common mistakes when implementing the backtracking search for this problem?

Common mistakes include allowing leading zeros, miscalculating the next digit by ignoring k, and not pruning invalid branches early.

terminal

Solution

Solution 1: DFS

We can enumerate the first digit of all numbers of length $n$, and then use the depth-first search method to recursively construct all numbers that meet the conditions.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
        def dfs(x: int):
            if x >= boundary:
                ans.append(x)
                return
            last = x % 10
            if last + k <= 9:
                dfs(x * 10 + last + k)
            if last - k >= 0 and k != 0:
                dfs(x * 10 + last - k)

        ans = []
        boundary = 10 ** (n - 1)
        for i in range(1, 10):
            dfs(i)
        return ans

Continue Practicing

#1096 brace expansion ii #797 all paths from source to target #773 sliding puzzle