967. Numbers With Same Consecutive Differences

class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 1; i < 10; i++) {
            backtrack(ans, i, 2, i + k, n, k);
            if (k != 0) {
                backtrack(ans, i, 2, i - k, n, k);
            }
        }
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }

    private void backtrack(List<Integer> ans, int num, int pos, int currDigit, int n, int k) {
        if (currDigit < 0 || currDigit > 9) {
            return;
        }
        int currNum = num * 10 + currDigit;
        if (pos == n) {
            ans.add(currNum);
            return;
        }
        backtrack(ans, currNum, pos + 1, currDigit + k, n, k);
        if (k != 0) {
            backtrack(ans, currNum, pos + 1, currDigit - k, n, k);
        }
    }
}

Backtrack. DFS. 需要注意k等于0的edge case.

时间复杂度: O(2^n)
空间复杂度: O(2^n)