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
};
'๐ Study Note > LeetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
346. Moving Average from Data Stream (0) | 2022.12.26 |
---|---|
2225. Find Players With Zero or One Losses (0) | 2022.11.28 |
49. Group Anagrams (0) | 2022.11.26 |
216. Combination Sum III (0) | 2022.11.24 |
39. Combination Sum (0) | 2022.11.24 |