Backtracking Problems

function solveNQueens(n) {
    let result = [];
    let board = new Array(n).fill().map(() => new Array(n).fill('.'));
    let cols = new Array(n).fill(false), diag1 = new Array(2*n - 1).fill(false), diag2 = new Array(2*n - 1).fill(false);

    function backtrack(row) {
        if (row === n) {
            result.push(board.map(r => r.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (cols[col] || diag1[row - col + n - 1] || diag2[row + col]) continue;
            board[row][col] = 'Q';
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = true;
            backtrack(row + 1);
            board[row][col] = '.';
            cols[col] = diag1[row - col + n - 1] = diag2[row + col] = false;
        }
    }

    backtrack(0);
    return result;
}
        

function solveSudoku(board) {
    function isValid(board, row, col, num) {
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === num || board[i][col] === num) return false;
            if (board[Math.floor(row / 3) * 3 + Math.floor(i / 3)][Math.floor(col / 3) * 3 + i % 3] === num) return false;
        }
        return true;
    }
    
    function backtrack(board) {
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                if (board[row][col] === '.') {
                    for (let num = 1; num <= 9; num++) {
                        if (isValid(board, row, col, num.toString())) {
                            board[row][col] = num.toString();
                            if (backtrack(board)) return true;
                            board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    backtrack(board);
}
        

function subsets(nums) {
    let result = [];
    function backtrack(start, current) {
        result.push([...current]);
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    backtrack(0, []);
    return result;
}
        

function permute(nums) {
    let result = [];
    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]]; // Swap
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]]; // Backtrack
        }
    }
    backtrack(0);
    return result;
}
        

function combine(n, k) {
    let result = [];
    function backtrack(start, current) {
        if (current.length === k) {
            result.push([...current]);
            return;
        }
        for (let i = start; i <= n; i++) {
            current.push(i);
            backtrack(i + 1, current);
            current.pop();
        }
    }
    backtrack(1, []);
    return result;
}
        

function solveMaze(maze, start, end) {
    let N = maze.length;
    let result = [];
    let visited = Array.from({length: N}, () => Array(N).fill(false));

    function backtrack(x, y, path) {
        if (x === end[0] && y === end[1]) {
            result.push([...path]);
            return;
        }
        if (x < 0 || y < 0 || x >= N || y >= N || maze[x][y] === 0 || visited[x][y]) return;
        visited[x][y] = true;
        path.push([x, y]);

        backtrack(x + 1, y, path);
        backtrack(x - 1, y, path);
        backtrack(x, y + 1, path);
        backtrack(x, y - 1, path);

        path.pop();
        visited[x][y] = false;
    }

    backtrack(start[0], start[1], []);
    return result;
}
        

function hamiltonianPath(graph, start) {
    let N = graph.length;
    let visited = Array(N).fill(false);
    let path = [];

    function backtrack(v) {
        path.push(v);
        visited[v] = true;
        
        if (path.length === N) return true;
        for (let i = 0; i < N; i++) {
            if (graph[v][i] === 1 && !visited[i]) {
                if (backtrack(i)) return true;
            }
        }
        
        visited[v] = false;
        path.pop();
        return false;
    }

    return backtrack(start) ? path : [];
}
        

function subsetSum(nums, target) {
    let result = [];
    function backtrack(start, currentSum, current) {
        if (currentSum === target) {
            result.push([...current]);
            return;
        }
        if (currentSum > target) return;
        for (let i = start; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1, currentSum + nums[i], current);
            current.pop();
        }
    }
    backtrack(0, 0, []);
    return result;
}
        

function exist(board, word) {
    let m = board.length, n = board[0].length;

    function dfs(i, j, index) {
        if (index === word.length) return true;
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] !== word[index]) return false;

        let temp = board[i][j];
        board[i][j] = '#'; // Mark as visited

        let res = dfs(i + 1, j, index + 1) || dfs(i - 1, j, index + 1) ||
                 dfs(i, j + 1, index + 1) || dfs(i, j - 1, index + 1);

        board[i][j] = temp; // Restore
        return res;
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }

    return false;
}
        

function combinationSum(candidates, target) {
    let result = [];
    function backtrack(start, currentSum, current) {
        if (currentSum === target) {
            result.push([...current]);
            return;
        }
        if (currentSum > target) return;
        for (let i = start; i < candidates.length; i++) {
            current.push(candidates[i]);
            backtrack(i, currentSum + candidates[i], current);
            current.pop();
        }
    }
    backtrack(0, 0, []);
    return result;
}
        

function partition(s) {
    let result = [];
    function backtrack(start, current) {
        if (start === s.length) {
            result.push([...current]);
            return;
        }
        for (let end = start + 1; end <= s.length; end++) {
            let sub = s.slice(start, end);
            if (sub === sub.split('').reverse().join('')) {
                current.push(sub);
                backtrack(end, current);
                current.pop();
            }
        }
    }
    backtrack(0, []);
    return result;
}
        

function diffWaysToCompute(input) {
    let result = [];
    
    function calculate(left, right, op) {
        if (op === '+') return left + right;
        if (op === '-') return left - right;
        if (op === '*') return left * right;
    }
    
    for (let i = 0; i < input.length; i++) {
        if (['+', '-', '*'].includes(input[i])) {
            let left = diffWaysToCompute(input.slice(0, i));
            let right = diffWaysToCompute(input.slice(i + 1));
            
            for (let l of left) {
                for (let r of right) {
                    result.push(calculate(l, r, input[i]));
                }
            }
        }
    }
    
    if (result.length === 0) result.push(Number(input));
    return result;
}