967.md

967. Numbers With Same Consecutive Differences

Solution 1 (O(2^n))

# DFS
class Solution(object):
    def numsSameConsecDiff(self, N, K):
        """
        :type N: int
        :type K: int
        :rtype: List[int]
        """
        ans = []
        if N == 1:
            ans.append(0)

        def dfs(num, cnt):
            if cnt == N:
                ans.append(int(num))
                return
            last_num = int(num[-1])
            if K == 0:
                dfs(num + str(last_num), cnt + 1)
                return
            for cur_num in [last_num + K, last_num - K]:
                if 0 <= cur_num <= 9:
                    dfs(num + str(cur_num), cnt + 1)

        for i in range(1, 10):
            dfs(str(i), 1)
        return ans