967. Numbers With Same Consecutive Differences

967. Numbers With Same Consecutive Differences

Medium

---

Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order.

Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

 

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.

 

Constraints:

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

0 ~ 9까지의 숫자를 사용하여 길이가 n이고, 연속되는 숫자의 차이가 k인 수를 구하는 문제이다.

이 문제는 n <= 15이고 전체를 탐색하면서 가지치기를 해야 하기 때문에 백트래킹으로 풀 수 있는 문제이다.

 

백트래킹의 의사코드는 

1. path의 길이가 1 이상일 때( 두 개를 비교 가능) 연속되는 두 숫자의 차이를 구한다, 이때 k가 아니라면 return

2. path 의 길이가 n일 경우 ans에 푸시한다.

3. for문을 순회한다.

4. 0이 앞에 올 수 없으므로 (01 불가능) path의 길이가 0이고 i 가 0일 때 continue

5. path에 해당 숫자 푸시후 재귀를 통해 반복 

 

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function(n, k) {
    const backtrack = (path) => {
        if(path.length > 1 && Math.abs(path.at(-2) - path.at(-1)) !== k) return 
        if(path.length === n){
            ans.push(path.join(''))
            return
        }
        for(let i=0; i<=9; i++){
            if(path.length === 0 && i === 0) continue
            path.push(i)
            backtrack(path)
            path.pop()
        }
    }
    
    const ans = [] 
    backtrack([])
    
    return ans
};