Tasks

Backtracking

Index	Task Name	Task Number	Difficulty	Link
1	Letter Combinations of a Phone Number	17	Medium	Link
2	Combination Sum	39	Medium	Link
3	Generate Parentheses	22	Medium	Link
4	Permutations	46	Medium	Link
5	Subsets	78	Medium	Link
6	Word Search	79	Medium	Link
7	N-Queens	51	Hard	Link
8	Sudoku Solver	37	Hard	Link
9	Palindrome Partitioning	131	Medium	Link
10	Restore IP Addresses	93	Medium	Link
11	House Robber III	337	Medium	Link
12	Matchsticks to Square	473	Medium	Link

// 79. Word Search

// Time: O(n * 3^l) | Space: O(l)
var exist = function(board, word) {
    const m = board.length;
    const n = board[0].length;

    for (let row = 0; row < m; row++) {
        for (let col = 0; col < n; col++) {
            const result = dfs(row, col, word, board);
            if (result) {
                return true;
            }
        }
    }
    return false;
};

function dfs(row, col, word, grid) {
    // The full word is found.
    if (word.length === 0) {
        return true;
    }
    const outOfRow = row < 0 || row === grid.length;
    const outOfCol = col < 0 || col === grid[0].length;

    // Out of grid.
    if (outOfRow || outOfCol) {
        return false;
    }
    // Letter does not match.
    const letterNotMatch = grid[row][col] !== word[0];
    if (letterNotMatch) {
        return false;
    }
    // Steps to go throug.
    const offsets = [
        [0, -1], // top
        [1, 0],  // right
        [0, 1],  // bottom
        [-1, 0]  // left
    ];
    let result = false;

    // Mark current cell as visited.
    grid[row][col] = '*';

    // Try every direction for the next letter.
    for (let offset of offsets) {
        const rowOffset = offset[0];
        const colOffset = offset[1];
        result = dfs(
            row + rowOffset,
            col + colOffset,
            word.substring(1), // to start with the next letter to search
            grid,
        );
        // The match is found.
        if (result) {
            break;
        }
    }
    // Reset char from * back to its initial state.
    grid[row][col] = word[0];
    return result;
}

/*
Backtracking. DFS.
------------------------------
Main function.
1. Iterate over every cell in the grid.
2. Run DFS for every cell.
3. Return true if result is found.
4. Return false if result is not found.

DFS
1. Return true if result is found (in our case we substring to the empty string).
2. Check out of boundaries and no match cases. Return false in this case.
3. Mark current char as visited and go in every direction with DFS to check next variants.
4. Break the loop once the result is found.
5. Return result.
------------------------------
Time: O(n * 3^l)
Space: O(l)
Where n is the number of cells and l is the length of the word we are searching for.
*/

// 51. N-Queens

// Time: O(n^2) | Space: O(n)
var solveNQueens = function(n) {
    const result = [];
    backtracking(0, [], n, result);
    return result;
};

/*
currentRow  -> row in the current backtracking iteration.
solution    -> the list of queens poisitons. Index is row and value is column.
n           -> number of queens/size of board.
result      -> the final result array. 
*/
function backtracking(currentRow, solution, n, result) {
    // It means we have valid solution.
    if (currentRow === n) {
        const board = generateBoard(solution);
        result.push(board);
        return;
    }
    // Try to place a queen in every column in the current row.
    for (let col = 0; col < n; col++) {
        solution.push(col);

        if (isValid(solution)) {
            const nextRow = currentRow + 1;
            backtracking(nextRow, solution, n, result);
        }
        solution.pop();
    }
}

// Convert row/col indexes array to the result-expected string.
function generateBoard(solution) {
    const n = solution.length;
    const board = [];

    for (let row = 0; row < n; row++) {
        let boardRow = '';
        for (let col = 0; col < n; col++) {
            // If we have queen on this row/col position.
            if (col === solution[row]) {
                boardRow += 'Q';
            } else {
                boardRow += '.';
            }
        }
        board.push(boardRow);
    }
    return board;
}

function isValid(solution) {
    const lastRow = solution.length - 1;
    const newQueenPosition = solution[lastRow];

    // Check row/column position collision for every Queen in the current solution.
    for (let row = 0; row < lastRow; row++) {
        const prevQueenPosition = solution[row];

        const rowDistance = lastRow - row;
        const colDistance = Math.abs(newQueenPosition - prevQueenPosition);

        const isSameColumn = colDistance === 0;
        const isSameDiagonal = rowDistance === colDistance;
        if (isSameColumn || isSameDiagonal) {
            return false;
        }
    }
    return true;
}

/*
Backtracking
--------------------------------
1. Iterate through every row (our row + 1 backtracking param).
2. Iterate through every column.
3. Push queen at row/col position to the solution.
4. Check if the current solution is valid and if yes -> add the next row queen.
5. Pop the last added position at the end of every cycle.
--------------------------------
Time: O(n^2) | Space: O(n)
*/

// 37. Sudoku Solver

// Time: O(b^d), Space: O(1)
var solveSudoku = function(board) { 
    backtrack(board);
};

const N = 9; // Size of the Sudoku board   

function isValid(board, row, col, num) {
    // Check if the number conflicts with the same number in the same row
    for (let i = 0; i < N; i++) {
        if (board[row][i] === num) {
            return false;
        }
    }
    // Check if the number conflicts with the same number in the same column
    for (let i = 0; i < N; i++) {
        if (board[i][col] === num) {
            return false;
        }
    }
    // Check if the number conflicts with the same number in the 3x3 subgrid
    const startRow = Math.floor(row / 3) * 3;
    const startCol = Math.floor(col / 3) * 3;

    for (let i = startRow; i < startRow + 3; i++) {
        for (let j = startCol; j < startCol + 3; j++) {
            if (board[i][j] === num) {
                return false;
            }
        }
    }
    return true;
}

function backtrack(board) {
    for (let row = 0; row < N; row++) {
        for (let col = 0; col < N; col++) {
            if (board[row][col] !== '.') {
                continue;
            }
            for (let num = 1; num <= 9; num++) {
                const numStr = num.toString();
                const numIsValid = isValid(board, row, col, numStr);
                if (!numIsValid) {
                    continue;
                }
                board[row][col] = numStr;
                if (backtrack(board)) {
                    return true;
                }
                // Backtrack in case previous sequence is invalid.
                board[row][col] = '.';
            }
            return false;
        }
    }
    // All cells are filled
    return true;
}

/*
Backtracking.
------------------------------------
First explanation
--------------------
1. Iterate over each cell in the board.
2. If the current cell is empty (contains '.'), try all possible numbers from 1 to 9 to fill the cell.
3. Check if the chosen number is valid in the current position by checking if it conflicts with the numbers in the same row, column, or 3x3 subgrid.
4. If the chosen number is valid, assign it to the current cell and recursively call backtrack for the next empty cell.
5. After the recursive call, if the Sudoku puzzle is solved (all cells are filled), return true to propagate the success back to the previous recursive call.
6. If the Sudoku puzzle is not solved, remove the assigned number from the current cell and try the next possible number.
7. If all numbers from 1 to 9 have been tried and none of them resulted in a solution, return false to backtrack and try different numbers in the previous cells.
--------------------
Second explanation
--------------------
1. Given a sudoku board, start from the upper left cell.
2. Proceed to the first free cell.
3. Iterate over the numbers from 1–9, and try to put each number in the cell.
4. If the number is not yet in the current row, column, and 3 x 3 sub-box, first place the number in a cell.
5. Write down that number that is now present in the current row, column, and box.
6. If we reach the last cell, that means we’ve successfully solved the sudoku.
7. Else, we move to the next cell.
8. Backtrack if the solution is not yet present, and remove the last number from the cell.
------------------------------------
Time: 
O(b^d), where b is the branching factor (the number of possibilities for each decision) and d is the depth of the recursion (the number of empty cells). Worst case: O(9^81).
Space: O(1).
*/

// 93. Restore IP Addresses

// Time: O(1) | Space: O(1)
var restoreIpAddresses = function(s) {
    if (s.length < 4 || s.length > 12) {
        return [];
    }
    const result = [];
    backtrack(s, 0, 4, '', result);
    return result;
};

/**
 * @param {string} s            -> our input string
 * @param {number} start        -> the starting index (start from 0)
 * @param {number} partsLeft    -> the number of parts remaining to form (start from 4)
 * @param {string} path         -> the current IP address being built
 * @param {number} result       -> the result list of IP addresses
 * @return {string[]}
 */
function backtrack(s, start, partsLeft, path, result) {
    // We construct 4 parts.
    if (partsLeft === 0) {
        // There are no more characters in a string.
        if (start === s.length) {
            // So the current IP is valid and we add it to the result.
            result.push(path);
        }
        return;
    }
    // Iterate over the next three characters in the string, starting from the start index, 
    // and try all possible combinations for the current part of the IP address.
    for (let i = 1; i <= 3; i++) {
        
        // To slice string to get new segment to try.
        const end = start + i;

        if (end > s.length) {
            break;
        }
        // Possible next segment might be 1, 2, 3 numbers based on i.
        const segment = s.slice(start, end);

        // Validate segment.
        const invalidRange = parseInt(segment) > 255;
        const leadingZero = segment.length > 1 && segment[0] === '0';

        if (invalidRange || leadingZero) {
            break;
        }

        // Use every valid segment as part of the possible solution.
        const newPath = path === '' 
            ? segment 
            : path + '.' + segment;
        backtrack(s, end, partsLeft - 1, newPath, result);
    }
}

/*
 * Backtracking
 * --------------------------
 1. Iterate through the string using recursive backtracking.
 2. Starting from first element try to add 1, 2, 3 elements to the IP part 
 and proceed with this solution.
 3. Every next recursive call continue with previous valid part.
 * --------------------------
 * Time: O(1) | Space: O(1)
 */

// 337. House Robber III

// Time: O(n) | Space: O(n)
var rob = function(root) {
    const result = dfs(root);
    return Math.max(...result);
};

function dfs(root) {
    // Empty tree case.
    if (root === null) {
        return [0, 0];
    }
    // Recursively calculating the maximum amount 
    // that can be robbed from the left subtree of the root.
    const leftSubtree = dfs(root.left);
    
    // Recursively calculating the maximum amount 
    // that can be robbed from the right subtree of the root.    
    const rightSubtree = dfs(root.right);
    
    // includeRoot contains the maximum amount of money 
    // that can be robbed with the parent node included.
    const includeRoot = root.val + leftSubtree[1] + rightSubtree[1];
    
    // excludeRoot contains the maximum amount of money 
    // that can be robbed with the parent node excluded.
    const leftMax = Math.max(...leftSubtree);
    const rightMax =  Math.max(...rightSubtree);
    const excludeRoot = leftMax + rightMax;

    return [includeRoot, excludeRoot];
}

/*
Backtracking. Greedy. DFS.
--------------------------------
In [withRoot, withoutRoot] we keep nodes sum with root on the left and without on the right.
The final "with root" val is Math.max(root.val + leftWithoutRoot + rightWithoutRoot).
Final "without root" val is sum of left and right.
--------------------------------
Time: O(n) | Space: O(n)
*/

// 473. Matchsticks to Square

// Time: O(n log n) | Space: O(n)
var makesquare = function(matchsticks) {
    // We should have at least 4 matchsticks to form a square.
    if (matchsticks.length < 4) {
        return false;
    }

    const totalLength = matchsticks.reduce((acc, curr) => acc + curr, 0);

    // We will not be able to form a square if total length is not a multiple of 4.
    if (totalLength % 4 !== 0) {
        return false;
    }

    // The square side target size.
    const target = totalLength / 4;

    // Sort nums in DESC order.
    matchsticks.sort((a, b) => b - a);

    return backtrack(matchsticks, target, 4, 0, 0);
};

function backtrack(nums, target, sides, index, currentSum) {
    // All sides are complited.
    if (sides === 0) {
        return true;
    }
    // We form the next side.
    if (currentSum === target) {
        return backtrack(nums, target, sides - 1, 0, 0);
    }
    // Iterate over all matchsticks.
    for (let i = index; i < nums.length; i++) {

        // Continue if current stick is used or we overflow the target with it.
        if (nums[i] === -1 || nums[i] + currentSum > target) {
            continue;
        }

        // Remember the original length of the stick.
        const originalLength = nums[i];
        
        // Mark current stick as used.
        nums[i] = -1;

        const nextIndex = i + 1;
        const nextSum = currentSum + originalLength;
        const stickUsageIsValid = backtrack(nums, target, sides, nextIndex, nextSum);

        // If all next recursive iterations are valid -> the current stick is also valid.
        if (stickUsageIsValid) {
            return true;
        }

        // In case usage of some next iterations are invalid and we need to use stick differently.
        nums[i] = originalLength;
    }

    // In case we check all possible stick usage variations and do not achive the result.
    return false;
}

/*
Backtracking
------------------------------
1. Return false if less than 4 matchsticks.
2. Return false if all matchsticks length is less than 4.
3. The square side size is must be 1/4 of total length.
4. Sort sticks in the DESC order to use in backtracking.
5. Return the backtrack result.

---------------
Backtrack
---------------
1. If sides becomes 0, it means we have formed all the sides with the given matchsticks. We check if the current sum is equal to the target length target. If it is, return true to indicate that a valid square has been formed.
2. If the current sum is equal to the target length target, it means we have formed one side. We increment the sides count and reset the currentSum to 0, and recursively call backtrack for the next side starting from the beginning of the matchstick lengths array.
3. Iterate over the remaining matchsticks starting from the index and try all possible combinations to form the current side.
3.1. If the current matchstick length plus the current sum is greater than the target length target, or if the matchstick length is already used (marked as -1), continue to the next iteration.
3.2. Otherwise, mark the current matchstick as used by setting its value to -1, and recursively call backtrack for the next matchstick with the updated parameters.
3.3. After the recursive call, if it returns true, it means a valid square has been formed. Return true to propagate the success back to the previous recursive call.
3.4. If the recursive call returns false, backtrack by marking the current matchstick as unused by setting its value back to the original length, and try the next matchstick.
------------------------------
Time: O(n log n) | Space: O(1)
*/