Recursion basics

[bibin-jaimon]

Use recursion visualizer: https://recursion.vercel.app/

https://leetcode.com/problems/n-th-tribonacci-number/

var tribonacci = function(n) {
    if (n == 0) { 
        return 0 
    }
    if (n <= 2) { 
        return 1 
    }

    const a = tribonacci(n-1)
    const b = tribonacci(n-2)
    const c = tribonacci(n-3)
    return  a + b + c
};

https://leetcode.com/problems/climbing-stairs/

var climbStairs = function(n) {
    if (n < 2) return 1
    const waysTillLastStep = climbStairs(n-1)
    const waysTillSecondLastStep = climbStairs(n-2)
    return waysTillLastStep + waysTillSecondLastStep
};

https://leetcode.com/problems/min-cost-climbing-stairs/

const helper = (cost, index) => {

    if (index >= cost.length) return 0

    const oneJumpCost = helper(cost, index + 1) 
    const twoJumpCost = helper(cost, index + 2)
    const minCost = Math.min(oneJumpCost, twoJumpCost)
    return minCost + cost[index]

 }
var minCostClimbingStairs = function(cost) {

    const costAtFirstStair = helper(cost, 0)
    const costAtSecondStair = helper(cost, 1)
    return Math.min(costAtFirstStair, costAtSecondStair)
};

https://leetcode.com/problems/subsets/

const helper = (nums, index, res, [...current]) => {

    if (index == nums.length) {
        res.push(current)
        return
    }

    // exclude
    helper(nums, index+1, res, current)

    // include
    current.push(nums[index])
    helper(nums, index+1, res, current) 

}

var subsets = function(nums) {
    const res = []
    helper(nums, 0, res, [])
    return res
};

https://leetcode.com/problems/house-robber-ii/

const helper = (nums, index) => {
    if (index >= nums.length) { return 0 }
    const rob = nums[index] + helper(nums, index+2)
    const dontRob = helper(nums, index+1)
    return Math.max(rob, dontRob)
}

var rob = function(nums) {
    if (nums.length == 1) { return nums[0] }
    // avoid first element and rob the houses
    const dontRobFirst = helper(nums, 1)
    // avoid last element and rob the houses
    nums.pop()
    const robFirst = helper(nums, 0)
    return Math.max(dontRobFirst, robFirst)
};

https://leetcode.com/problems/generate-parentheses/

const helper = (result, n, openCount, closeCount, current) => {

    if (closeCount == n) {
        result.push(current)
        return
    }

    if (openCount < n) {
        helper(result, n, openCount+1, closeCount, current + "(")
    }

    if (closeCount < openCount) {
        helper(result, n, openCount, closeCount+1, current + ")")
    } 
}

var generateParenthesis = function(n) {
    const res = []
    helper(res, n, 0, 0, "")
    return res
};

https://leetcode.com/problems/decode-ways/description/

// Top - Down
const helper = (message, index) => {

    //base case
    if (index >= message.length) {
        return 1
    }

    let res = 0

    //single digit
    if (message[index] != 0) {
        res += helper(message, index+1)
    }

    const isBetween10to19 = message[index] == 1 && message[index+1] != undefined
    const isBetween20to26 = (message[index] == 2 && 0 <= message[index+1] && message[index+1] <= 6)

    if (isBetween10to19 || isBetween20to26) {
        res += helper(message, index+2)
    } 

    return res
}

var numDecodings = function(s) {
    if (s[0] == 0) {return 0}
    return helper(s, 0)
};

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

const dial = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz'
}

const helper = (digits, res, current, index) => {

    if (index == digits.length) {
        res.push(current)
        return
    }

    const mapping = dial[digits[index]]

    for (char of mapping) {
        helper(digits, res, current+char, index+1)
    }
}

var letterCombinations = function(digits) {
    const res = []
    if (digits != "") {
        helper(digits, res, "", 0)
    }
    return res   
};

https://leetcode.com/problems/decode-string/

const isNumber = number => isNaN(Number(number)) == false

var decodeString = function(s) {
        let index = 0

        // Put helper inside the main function to use same index variable in every recurssion
        const helper = (message, res) => {
            let count = 0
            while (index < message.length) {
                const item = message[index]

                if (isNumber(item) == true) {
                    count = count*10 + Number(item)
                } else if (item == '[') {
                    index += 1
                    let innerString = helper(message, "")
                    while(count--) {
                        res += innerString
                    }

                    count = 0 
                } else if (item == ']') {
                    return res
                } else {
                    res += item
                }
                index += 1
            }

        return res
    }

    return helper(s, "")
};

[bibin-jaimon]

https://leetcode.com/problems/n-queens/description/

const isValid = (board, col, row) => {

    // check horizontal
    for (let i = 0; i < col; i++) {
        if (board[row][i] == 'Q') { return false } 
    }
    // check vertical - not required because we fill colm wise so in one col one q there 

    // check diagonal
    // left upper

    for (let r = row, c=col; r >=0 && c>=0; r--, c--) {
        if (board[r][c] == 'Q') { return false }
    }

    // left lower
    for (let r = row, c=col; c>=0 && r<board.length ; c--, r++) {
        if (board[r][c] == 'Q') { return false }
    }

    return true
}

const helper = (col, n, board, res) => {

    if (col === n) {
        res.push(board.map(item => item.join('')))
        return
    }

    for (let row=0; row < n; row++) {
        // check if board is valid
        if (isValid(board, col, row) == true) {
            board[row][col] = 'Q'
            helper(col+1, n, board, res)
            board[row][col] = '.'
        }
    }
}

var solveNQueens = function(n) {
    // create row or column
    // create board
    // call helper to get result
    const row = Array(n).fill('.')
    const board = []
    const res = []
    let q = n
    while(q--) {
        board.push([...row])
    }
    helper(0, n, board, res)
    return res
};

[bibin-jaimon]

https://leetcode.com/problems/sudoku-solver/description/

var solveSudoku = function(board) {

    const isValid = (board, row, col, digit) => {

        for (let i = 0; i < 9; i++) {
            if (board[row][i] == digit.toString()) return false

            if (board[i][col] == digit.toString()) return false

            const currentRow = (3*parseInt(row/3)) + parseInt(i/3)
            const currentCol = (3*parseInt(col/3)) + i%3
            if (board[currentRow][currentCol] == digit.toString()) return false
        }

        return true
    }

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                for (let digit = 1; digit <= 9; digit++) {
                    if (isValid(board, i, j, digit) == true) {
                        board[i][j] = digit.toString()
                        if (solveSudoku(board)) return true
                        board[i][j] = '.'
                    }
                }
                return false
            }
        }
    }

    return true
};