https://leetcode.com/problems/numbers-with-same-consecutive-differences/

numsWithSameConsecutiveDiff.js

/*
IDEA: We can build up a valid solution from left to right.
- Start with every legal number (1-9)
- For each starting point
  - append N+K, and keep building if legal
  - append N-K, and keep building if legal
- If you get to K digits, this is an answer, so add it to your result

Time Complexity:
- This is a recursive function with a branching factor of 2 and a
  maximum depth of K, so O(2^K)
*/
var numsSameConsecDiff = function(N, K) {
    
    const [result, wc] = [[], []];
    
    const build = () => {
        
        const last = wc[wc.length-1];
        if(last < 0 || last > 9) return;
        if(wc.length === N) return result.push(wc.join(''));
        
        wc.push(last + K); // try last + K
        build();
        wc.pop(); // backtrack
        
        if(!K) return; // edge case here. If K === 0, we don't want to try both N+K and N-K
        
        wc.push(last - K); // try last - K
        build();
        wc.pop(); // backtrack
    };
    
    for(let i=1; i<=9; i++){ // try every legal starting point
        wc.push(i); // start with i
        build(); // try building an answer
        wc.pop(); // backtrack: remove i, and try something else
    }
    
    if(N === 1) result.push('0');
    return result.map((digits) => parseInt(digits, 10));
};