Solution in C++:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    void backtrack(vector<int>& nums, vector<int>& path, 
                   vector<bool>& used, vector<vector<int>>& result) {
        // Base case: permutation complete
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        
        // Try each unused element
        for (int i = 0; i < nums.size(); i++) {
            if (!used[i]) {
                // Choose: add to path and mark as used
                used[i] = true;
                path.push_back(nums[i]);
                
                // Explore: recursively build rest of permutation
                backtrack(nums, path, used, result);
                
                // Unchoose: backtrack
                path.pop_back();
                used[i] = false;
            }
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        backtrack(nums, path, used, result);
        return result;
    }
};

Step-by-Step Simulation (nums = [1, 2]):

Explanation: We build permutations by choosing each element as the next element in the permutation. For each choice, we recursively build the rest of the permutation with the remaining elements. After exploring, we backtrack by removing the choice and trying the next option. When no elements remain, we have a complete permutation. The used array tracks which elements are already in the current path to avoid duplicates.

Time Complexity: O(n! × n)

Space Complexity: O(n! × n) for output

Solution in C++:

#include <vector>
using namespace std;

class Solution {
public:
    void backtrack(vector<int>& nums, int start, vector<int>& path, 
                   vector<vector<int>>& result) {
        // Add current subset to result
        result.push_back(path);
        
        // Try including each remaining element
        for (int i = start; i < nums.size(); i++) {
            // Choose: include nums[i]
            path.push_back(nums[i]);
            
            // Explore: generate subsets from remaining elements
            backtrack(nums, i + 1, path, result);
            
            // Unchoose: backtrack
            path.pop_back();
        }
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(nums, 0, path, result);
        return result;
    }
};

Step-by-Step Simulation (nums = [1, 2]):

Explanation: We generate subsets by either including or excluding each element. At each step, we add the current subset to results, then for each remaining element, we include it and recursively generate subsets from the remaining elements. We use a start index to avoid duplicates and ensure we only consider elements after the current position. This ensures we generate all 2^n subsets exactly once.

Time Complexity: O(2^n × n)

Space Complexity: O(2^n × n)

Solution in C++:

#include <vector>
#include <string>
using namespace std;

class Solution {
private:
    vector<vector<string>> result;
    vector<string> board;
    int n;
    
    bool isValid(int row, int col) {
        // Check column above
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        
        // Check diagonal \ (top-left)
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        // Check diagonal / (top-right)
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        return true;
    }
    
    void backtrack(int row) {
        // Base case: all queens placed
        if (row == n) {
            result.push_back(board);
            return;
        }
        
        // Try placing queen in each column of current row
        for (int col = 0; col < n; col++) {
            if (isValid(row, col)) {
                // Choose: place queen
                board[row][col] = 'Q';
                
                // Explore: place queens in next row
                backtrack(row + 1);
                
                // Unchoose: backtrack
                board[row][col] = '.';
            }
        }
    }
    
public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        board = vector<string>(n, string(n, '.'));
        backtrack(0);
        return result;
    }
};

Explanation: We place queens row by row. For each row, we try placing a queen in each column. Before placing, we check if it's valid (no conflict with previously placed queens in the same column or diagonals). If valid, we place it and recurse to the next row. If we reach row n, we have a valid solution. We backtrack by removing the queen and trying the next column. The isValid function checks three directions: column above, top-left diagonal, and top-right diagonal.

Time Complexity: O(n!)

Space Complexity: O(n²)

Solution in C++:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    void backtrack(vector<int>& candidates, int start, int remaining,
                   vector<int>& path, vector<vector<int>>& result) {
        // Base case: found valid combination
        if (remaining == 0) {
            result.push_back(path);
            return;
        }
        
        // Pruning: remaining is negative
        if (remaining < 0) {
            return;
        }
        
        // Try each candidate starting from 'start'
        for (int i = start; i < candidates.size(); i++) {
            // Choose: add candidate to path
            path.push_back(candidates[i]);
            
            // Explore: try same candidate again (can reuse)
            backtrack(candidates, i, remaining - candidates[i], path, result);
            
            // Unchoose: backtrack
            path.pop_back();
        }
    }
    
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> path;
        backtrack(candidates, 0, target, path, result);
        return result;
    }
};

Explanation: We build combinations by trying each candidate. We can reuse candidates, so we pass the same start index (i) to allow using the same candidate again. We subtract the candidate from the remaining target. If remaining becomes 0, we found a valid combination. If it becomes negative, we prune that path. We backtrack by removing the candidate and trying the next one. This ensures we explore all possible combinations that sum to target.

Time Complexity: O(2^target)

Space Complexity: O(target)

Solution in C++:

#include <vector>
#include <string>
using namespace std;

class Solution {
private:
    bool backtrack(vector<vector<char>>& board, const string& word,
                   int row, int col, int index) {
        // Base case: matched all characters
        if (index == word.length()) {
            return true;
        }
        
        // Boundary check
        if (row < 0 || row >= board.size() || 
            col < 0 || col >= board[0].size()) {
            return false;
        }
        
        // Character doesn't match
        if (board[row][col] != word[index]) {
            return false;
        }
        
        // Mark as visited temporarily
        char temp = board[row][col];
        board[row][col] = '#';
        
        // Try all 4 directions
        int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        for (int i = 0; i < 4; i++) {
            int newRow = row + directions[i][0];
            int newCol = col + directions[i][1];
            if (backtrack(board, word, newRow, newCol, index + 1)) {
                return true;
            }
        }
        
        // Backtrack: restore cell value
        board[row][col] = temp;
        return false;
    }
    
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        
        // Try starting from each cell
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
};

Explanation: We start from each cell and try to match the word character by character. We mark visited cells temporarily (with '#') to avoid revisiting the same cell in the current path. We explore all 4 directions (up, down, left, right). If we match all characters, we return True. If a path fails, we backtrack by restoring the cell value and trying other paths. This ensures we explore all possible paths without getting stuck in cycles.

Time Complexity: O(m × n × 4^L) where L is word length

Space Complexity: O(L) for recursion stack