Skip to main content

Backtracking Problems

N-Queens​

✅ with hashing​

striver's video - code

Intuition​

Approach​

Complexity​

  • Time complexity: O(n.n!)
  • Space complexity: ?
    vector<vector<string>> ans;

    bool is_safe(vector<int> &primary_diagonal, vector<int> &secondary_diagonal, vector<int> &rw, vector<int> &cl, int row, int col, int n)
    {
        if (rw.at(row) == 1)
            return false;
        if (cl.at(col) == 1)
            return false;
        if (primary_diagonal.at(n + col - row) == 1)
            return false;
        if (secondary_diagonal.at(row + col) == 1)
            return false;
        return true;
    }

    void foo(vector<string> &board, int row, int n, vector<int> &primary_diagonal, vector<int> &secondary_diagonal, vector<int> &rw, vector<int> &cl)
    {
        if (row == n)
        {
            ans.emplace_back(board);
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (is_safe(primary_diagonal, secondary_diagonal, rw, cl, row, col, n)) // i.e. not being attacked
            {
                primary_diagonal.at(n + col - row) = 1;
                secondary_diagonal.at(row + col) = 1;
                rw.at(row) = 1;
                cl.at(col) = 1;
                board.at(row).at(col) = 'Q';
                foo(board, row + 1, n, primary_diagonal, secondary_diagonal, rw, cl);
                board.at(row).at(col) = '.';
                primary_diagonal.at(n + col - row) = 0;
                secondary_diagonal.at(row + col) = 0;
                rw.at(row) = 0;
                cl.at(col) = 0;
            }
        }
    }

    vector<vector<string>> solveNQueens(int n)
    {
        vector<string> board(n);
        string str(n, '.');
        for (int i = 0; i < n; i++)
        {
            board.at(i) = str;
        }

        vector<int> primary_diagonal(2 * n, 0);
        vector<int> secondary_diagonal(2 * n, 0);
        vector<int> rw(n, 0);
        vector<int> cl(n, 0);
        int row = 0;
        foo(board, row, n, primary_diagonal, secondary_diagonal, rw, cl);

        return ans;
    }

without hashing​

Intuition​

Approach​

Complexity​

  • Time complexity:

  • Space complexity:

Code​

class Solution
{
public:
    vector<vector<string>> ans;

    void add_board_to_ans(vector<vector<int>> &board)
    {
        int n = board.size();
        vector<string> tmp(n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board.at(i).at(j) == 0)
                {
                    tmp.at(i).push_back('.');
                }
                else if (board.at(i).at(j) == 1)
                {
                    tmp.at(i).push_back('Q');
                }
            }
        }

        ans.emplace_back(tmp);
    }

    bool is_attacked(int row, int col, vector<vector<int>> &board)
    {
        int n = board.size();
        // row
        for (int i = 0; i < n; i++)
        {
            if (board.at(row).at(i) == 1)
                return true;
        }

        // col
        for (int i = 0; i < n; i++)
        {
            if (board.at(i).at(col) == 1)
                return true;
        }

        // digonals
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if ((i + j == row + col) && (board.at(i).at(j) == 1))
                {
                    return true;
                }
                if ((j - i == col - row) && (board.at(i).at(j) == 1))
                {
                    return true;
                }
            }
        }

        return false;
    }

    void foo(int row, vector<vector<int>> &board, int n)
    {
        if (row == n)
        {
            add_board_to_ans(board);
            return;
        }
        for (int col = 0; col < n; col++)   // as we only need to place the Queen at a column, the "row" is already determined by the  `foo(row, board, n)`
        {
            if (!is_attacked(row, col, board))
            {
                board.at(row).at(col) = 1;
                foo(row + 1, board, n);
                board.at(row).at(col) = 0;
            }
        }
    }

    vector<vector<string>> solveNQueens(int n)
    {
        vector<vector<int>> board(n, vector<int>(n));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                board.at(i).at(j) = 0;
            }
        }

        foo(0, board, n);

        return ans;
    }
};

N Queens CSES​

int ans = 0;

bool is_safe(int row, int col, vector<int> &primary_diagonal, vector<int> &secondary_diagonal, vector<int> &rw, vector<int> &cl, int n)
{
    if (rw.at(row) == 1 || cl.at(col) == 1 || primary_diagonal.at(n + col - row) == 1 || secondary_diagonal.at(row + col) == 1)
    {
        return false;
    }
    return true;
}

void foo(vector<string> &board, int row, int n, vector<int> &primary_diagonal, vector<int> &secondary_diagonal, vector<int> &rw, vector<int> &cl)
{
    if (row == n)
    {
        ++ans;
        return;
    }
    for (int col = 0; col < n; col++)
    {
        if (is_safe(row, col, primary_diagonal, secondary_diagonal, rw, cl, n))
        {
            if (board.at(row).at(col) != '*')
            {
                primary_diagonal.at(n + col - row) = 1;
                secondary_diagonal.at(row + col) = 1;
                rw.at(row) = 1;
                cl.at(col) = 1;
                board.at(row).at(col) = '*';
                foo(board, row + 1, n, primary_diagonal, secondary_diagonal, rw, cl);
                board.at(row).at(col) = '.';
                primary_diagonal.at(n + col - row) = 0;
                secondary_diagonal.at(row + col) = 0;
                rw.at(row) = 0;
                cl.at(col) = 0;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 8;
    vector<string> board(n);
    for (auto &el : board)
    {
        string tmp;
        getline(cin, tmp);
        el = tmp;
    }

    vector<int> primary_diagonal(2 * n, 0);
    vector<int> secondary_diagonal(2 * n, 0);
    vector<int> rw(n, 0);
    vector<int> cl(n, 0);
    int row = 0;
    foo(board, row, n, primary_diagonal, secondary_diagonal, rw, cl);

    cout << ans;

    return 0;
}

Grids Path CSES​

int row_directions[] = {-1, 0, 1, 0}; // up right down left // to be used for getting all possible directionsin a for loop
int col_directions[] = {0, 1, 0, -1}; // up right down left
int ans = 0;

void foo(vector<vector<int>> &grid, int curRow, int curCol, string str, int strIndex, int n)
{
    // base case
    if (strIndex == (n * n - 1)) // as input-path is of size 48 , so the index is [0...47]
    {
        ++ans;
        return;
    }

    // split grid into two
    if ((grid.at(curRow).at(curCol - 1) == 1) && (grid.at(curRow).at(curCol + 1) == 1) && (grid.at(curRow - 1).at(curCol) != 1) && (grid.at(curRow + 1).at(curCol) != 1))
    { // top-bottom boundary, left-right both open
        return;
    }
    if ((grid.at(curRow - 1).at(curCol) == 1) && (grid.at(curRow + 1).at(curCol) == 1) && (grid.at(curRow).at(curCol - 1) != 1) && (grid.at(curRow).at(curCol + 1) != 1))
    { // left-right boundary,  top-bottom both open
        return;
    }

    // reached end without going through all the paths
    if (curRow == n && curCol == 1 && (strIndex != n * n - 1)) // as the grid is [9x9] and actually wanted at [1..7]
    {
        return;
    }

    grid.at(curRow).at(curCol) = 1; // this path is Done, Now going to 'next-path'

    /* if  'next-path' is already given*/
    if (str.at(strIndex) == 'U')
    {
        int nextRow = curRow - 1;
        if (!grid.at(nextRow).at(curCol))
        {
            foo(grid, nextRow, curCol, str, strIndex + 1, n);
        }
    }
    else if (str.at(strIndex) == 'R')
    {
        int nextCol = curCol + 1;
        if (!grid.at(curRow).at(nextCol))
        {
            foo(grid, curRow, nextCol, str, strIndex + 1, n);
        }
    }
    else if (str.at(strIndex) == 'D')
    {
        int nextRow = curRow + 1;
        if (!grid.at(nextRow).at(curCol))
        {
            foo(grid, nextRow, curCol, str, strIndex + 1, n);
        }
    }
    else if (str.at(strIndex) == 'L')
    {
        int nextCol = curCol - 1;
        if (!grid.at(curRow).at(nextCol))
        {
            foo(grid, curRow, nextCol, str, strIndex + 1, n);
        }
    }
    else if (str.at(strIndex) == '?') /* for '?' */
    {
        for (int i = 0; i < 4; i++)
        {
            int nextRow = curRow + row_directions[i];
            int nextCol = curCol + col_directions[i];
            if (grid.at(nextRow).at(nextCol) == 1)
                continue;
            // cerr << "" << curRow << "," << curCol << "   ";
            foo(grid, nextRow, nextCol, str, strIndex + 1, n);
            // for 0 .. row_direction[0]==-1 & col_direction[0]==0 - UP
            // for 1 .. col_direction[1]==1 & row_direction[1]==0 - RIGHT
            // for 2 .. row_direction[2]==1 & col_direction[2]==0 - DOWN
            // for 3 .. col_direction[3]==-1 & row_direction[3]==0 - RIGHT
        }
    }

    grid.at(curRow).at(curCol) = 0; // backtracking
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string str;
    cin >> str;

    int n = 7;
    vector<vector<int>> grid(n + 2, vector<int>(n + 2, 0));

    for (int i = 0; i < grid.size(); i++)
    {
        grid.at(0).at(i) = 1;
        grid.at(grid.size() - 1).at(i) = 1;
        grid.at(i).at(0) = 1;
        grid.at(i).at(grid.size() - 1) = 1;
    }

    int curRow = 1;
    int curCol = 1;
    int strIndex = 0;

    foo(grid, curRow, curCol, str, strIndex, n);
    cout << ans;

    return 0;
}
info
const int DIR_LEN = 4;
int dr[DIR_LEN] = {-1, 0, 1, 0};
int dc[DIR_LEN] = {0, 1, 0, -1};
const int PATH_LEN = 48; // length of all possible paths
int p[PATH_LEN];
const int GRID_SIZE = 9;
// added border to all four sides so a 7x7 becomes a 9x9
bool onPath[GRID_SIZE][GRID_SIZE];

int tryPath(int pathIdx, int curR, int curC)
{
    // Optimization 3
    if ((onPath[curR][curC - 1] && onPath[curR][curC + 1]) && (!onPath[curR - 1][curC] && !onPath[curR + 1][curC]))
        return 0;
    if ((onPath[curR - 1][curC] && onPath[curR + 1][curC]) && (!onPath[curR][curC - 1] && !onPath[curR][curC + 1]))
        return 0;

    if (curR == 7 && curC == 1)
    { // reached endpoint before visiting all
        if (pathIdx == PATH_LEN)
            return 1;
        return 0;
    }

    if (pathIdx == PATH_LEN)
        return 0;

    int ret = 0;
    onPath[curR][curC] = true;

    // turn already determined:
    if (p[pathIdx] < 4)
    {
        int nxtR = curR + dr[p[pathIdx]];
        int nxtC = curC + dc[p[pathIdx]];
        if (!onPath[nxtR][nxtC])
            ret += tryPath(pathIdx + 1, nxtR, nxtC);
    }
    // see Java solution for optimization 4 implementation
    else
    { // iterate through all four possible turns
        for (int i = 0; i < DIR_LEN; i++)
        {
            int nxtR = curR + dr[i];
            int nxtC = curC + dc[i];
            if (onPath[nxtR][nxtC])
                continue;
            ret += tryPath(pathIdx + 1, nxtR, nxtC);
        }
    }
    // reset and return
    onPath[curR][curC] = false;
    return ret;
}

int main()
{
    string line;
    getline(cin, line);

    // convert path to ints
    for (int i = 0; i < PATH_LEN; i++)
    {
        char cur = line[i];

        if (cur == 'U')
            p[i] = 0;
        else if (cur == 'R')
            p[i] = 1;
        else if (cur == 'D')
            p[i] = 2;
        else if (cur == 'L')
            p[i] = 3;
        else
            p[i] = 4; // cur == '?'
    }

    // set borders of grid
    for (int i = 0; i < GRID_SIZE; i++)
    {
        onPath[0][i] = true;
        onPath[8][i] = true;
        onPath[i][0] = true;
        onPath[i][8] = true;
    }
    // initialize the inside of the grid to be completely empty
    for (int i = 1; i <= 7; i++)
    {
        for (int j = 1; j <= 7; j++)
        {
            onPath[i][j] = false;
        }
    }

    int startIdx = 0;
    int startR = 1;
    int startC = 1; // always start path at (1, 1)
    int ans = tryPath(startIdx, startR, startC);
    cout << ans << endl;
}

string PARTITIONs​

Partition means the string is split into several parts and each part is a substring E.g.:

// Partitons of string "aab"
(a a b), (a ab), (aa b), (aab)

split a string to get all different of partitions

  • a for(i..) loop for taking substring from index, i+index
    • so, I can get all the substrings
void p(vector<string> vs, int index)
{
    cerr << index << ":";
    for (auto el : vs)
        cerr << el << ".";
}

void addPalindromePartitions(int index, string &s, vector<string> &substrings, vector<vector<string>> &allSubstrings)
{
    if (index == s.size())
    {
        allSubstrings.push_back(substrings);
    }
    for (int i = index; i < s.size(); ++i) // ⚠️ for starts from the `index` as [we want the substring to continue after the previous substring]
    {
                                            p(substrings, index); cerr << "  "; // just debugging

        substrings.push_back(s.substr(index, i - index + 1));

                                            p(substrings, index); cerr << "+   "; // just debugging

        addPalindromePartitions(i + 1, s, substrings, allSubstrings); //↷↷ calling recursion with the `updated` substrings
        substrings.pop_back();  // backtracking , Also, when one index is finished, the previous index will start from this Line ..
        // E.g.: when 3 is over, 2 will start from this line and thus another element will be removed from the substrings

                                            p(substrings, index); cerr << "-" << endl; // just debugging
    }
}

vector<vector<string>> partition(string s) {
    vector<vector<string>> allSubstrings;
    if (s.empty())
        return allSubstrings;

    vector<string> substrings;
    addPalindromePartitions(0, s, substrings, allSubstrings);

    return allSubstrings;
}

int main()
{
    string s1 = "aab";

    vector<vector<string>> result = partition(s1);

    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++)
            cout << result[i][j] << " ";
        cout << endl;
    }
}

Palindrome Partitions​

split a string to get all different of partitions

  • a for(i..) loop for taking substring from index, i+index
    • so, I can get all the substrings
  • check isPalindrome, only then add substr with those i and pos to the substrings
    • here, I am making changes to the substrings vector continuously & so, several times I am using previously added substrings also with new ones to create a new partition. And this approach is Correct as the substrings is only added to the partition_substrings after pos == n, that all possible charaters of the string are included in different substrings of the partition.
class Solution {
public:
    vector<vector<string>> partition_substrings;

    bool isPalindrome(const string& s, int start, int end) {
        while(start <= end) {
            if (s.at(start++) != s.at(end--))   // comparing from extreme cornerns. E.g.: "aab" .. ([0!=2] [1==1])
                return false;
        }
        return true;
    }

    void foo(const string& s, vector<string>& substrings, int pos) {
        if (pos == s.size()) {
            partition_substrings.emplace_back(substrings);
        }
        for (int i=pos; i<s.size(); i++)  // ⚠️ for starts from the `index` as [we want the substring to continue after the previous substring]
        {
            if (isPalindrome(s, pos, i))
            {
                substrings.emplace_back(s.substr(pos, i-pos+1));
                foo(s, substrings, i+1);     // ↷↷ calling recursion with the `updated` substrings
                substrings.pop_back();   // backtracking , Also, when one index is finished, the previous index will start from this Line ..
                                         // E.g.: when pos=3 is over, pos=2 will start from this line and thus another element will be removed from the substrings
            }
        }


    }

    vector<vector<string>> partition(string s) {
        vector<string> substrings;
        int pos = 0;
        foo(s, substrings, pos);

        return partition_substrings;
    }
};

Rat in a Maze​