深度优先搜索 (DFS)#

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它从一个起始节点开始，沿着一条路径尽可能深地探索，直到到达末端，然后回溯以探索其他分支。常用于寻找路径、连通性、环检测等。

Example Problem Leetcode 79. 单词搜索

原理： 在一个字符网格中寻找一个单词。我们可以从每个单元格开始，进行DFS，尝试匹配单词的每个字符。为了防止重复使用同一个单元格，我们可以在DFS递归时将当前单元格标记为已访问（例如，通过修改其值），并在回溯时恢复它。

#include <vector>
#include <string>

class Solution {
public:
    bool exist(std::vector<std::vector<char>>& board, std::string word) {
        if (board.empty()) return false;
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
private:
    bool dfs(std::vector<std::vector<char>>& board, const std::string& word, int r, int c, int k) {
        if (k == word.length()) return true;
        int rows = board.size(), cols = board[0].size();
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[k]) {
            return false;
        }

        char temp = board[r][c];
        board[r][c] = '#'; // Mark as visited

        bool found = dfs(board, word, r + 1, c, k + 1) ||
                     dfs(board, word, r - 1, c, k + 1) ||
                     dfs(board, word, r, c + 1, k + 1) ||
                     dfs(board, word, r, c - 1, k + 1);

        board[r][c] = temp; // Backtrack
        return found;
    }
};

Example Problem Leetcode 463. 岛屿的周长

原理： 计算一个由 1 组成的岛屿的周长。周长由岛屿单元格与水域（0）或网格边界相邻的边构成。

1. 遍历整个网格，找到岛屿的任意一个陆地单元格（值为 1）。
2. 从这个单元格开始进行DFS。
3. 对于当前单元格 (r, c)，检查其四个方向（上、下、左、右）：
   • 如果邻居是水域或超出边界，那么这条边就是周长的一部分，周长加1。
   • 如果邻居是未访问过的陆地，则递归地对该邻居进行DFS。
4. 为了避免重复计算，需要一个 visited 集合或直接修改原数组（例如，将访问过的 1 变为 2）。

#include <vector>

class Solution {
public:
    int islandPerimeter(std::vector<std::vector<int>>& grid) {
        if (grid.empty()) return 0;
        int rows = grid.size(), cols = grid[0].size();
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == 1) {
                    return dfs(grid, i, j);
                }
            }
        }
        return 0;
    }
private:
    int dfs(std::vector<std::vector<int>>& grid, int r, int c) {
        int rows = grid.size(), cols = grid[0].size();
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0) {
            return 1; // Edge contributes to perimeter
        }
        if (grid[r][c] == 2) { // Already visited
            return 0;
        }
        
        grid[r][c] = 2; // Mark as visited
        
        int perimeter = 0;
        perimeter += dfs(grid, r + 1, c);
        perimeter += dfs(grid, r - 1, c);
        perimeter += dfs(grid, r, c + 1);
        perimeter += dfs(grid, r, c - 1);
        
        return perimeter;
    }
};

Example Problem Leetcode 529. 扫雷游戏

原理： 模拟扫雷游戏的点击操作。

1. 如果点击到地雷（‘M’），游戏结束，将该位置变为 ‘X’。
2. 如果点击到空白方块（‘E’），需要揭示它以及所有相邻的空白方块。
   • 首先，计算点击位置周围8个方向的地雷数量。
   • 如果地雷数大于0，将该位置更新为数字，并停止扩展。
   • 如果地雷数为0，将该位置更新为 ‘B’（Blank），然后对周围8个方向的 ‘E’ 递归进行DFS。

#include <vector>

class Solution {
public:
    std::vector<std::vector<char>> updateBoard(std::vector<std::vector<char>>& board, std::vector<int>& click) {
        int r = click[0], c = click[1];
        if (board[r][c] == 'M') {
            board[r][c] = 'X';
            return board;
        }
        dfs(board, r, c);
        return board;
    }
private:
    void dfs(std::vector<std::vector<char>>& board, int r, int c) {
        int rows = board.size(), cols = board[0].size();
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != 'E') {
            return;
        }

        int mines = countMines(board, r, c);

        if (mines > 0) {
            board[r][c] = '0' + mines;
        } else {
            board[r][c] = 'B';
            for (int dr = -1; dr <= 1; ++dr) {
                for (int dc = -1; dc <= 1; ++dc) {
                    if (dr == 0 && dc == 0) continue;
                    dfs(board, r + dr, c + dc);
                }
            }
        }
    }

    int countMines(const std::vector<std::vector<char>>& board, int r, int c) {
        int mines = 0;
        for (int dr = -1; dr <= 1; ++dr) {
            for (int dc = -1; dc <= 1; ++dc) {
                if (dr == 0 && dc == 0) continue;
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < board.size() && nc >= 0 && nc < board[0].size() && board[nr][nc] == 'M') {
                    mines++;
                }
            }
        }
        return mines;
    }
};

广度优先搜索 (BFS)#

广度优先搜索（BFS）也是一种图遍历算法，它从根节点开始，探索完所有邻近节点后，再逐层向外扩展。BFS 常用于寻找最短路径（在无权图中）、层序遍历等。它通常使用队列来实现。

Example Problem Leetcode 127. 单词接龙

原理： 寻找从 beginWord 到 endWord 的最短转换序列长度。这是一个在隐式图中寻找最短路径的问题，图的节点是单词，如果两个单词只相差一个字母，则它们之间有边。BFS 是解决无权图最短路径问题的理想选择。

1. 将 wordList 存入哈希集合以便快速查找。
2. 从 beginWord 开始进行BFS，队列中存储 (单词, 转换次数)。
3. 在每一层，生成当前单词所有可能的“邻居”（只改变一个字母），如果在 wordList 中存在且未被访问过，则将其加入队列，并从 wordList 中移除以防重复访问。
4. 当第一次找到 endWord 时，其对应的转换次数就是最短长度。

#include <vector>
#include <string>
#include <queue>
#include <unordered_set>

class Solution {
public:
    int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
        std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord) == dict.end()) return 0;

        std::queue<std::pair<std::string, int>> q;
        q.push({beginWord, 1});
        
        while (!q.empty()) {
            auto [word, len] = q.front();
            q.pop();

            if (word == endWord) return len;

            for (int i = 0; i < word.length(); ++i) {
                char original_char = word[i];
                for (char c = 'a'; c <= 'z'; ++c) {
                    word[i] = c;
                    if (dict.count(word)) {
                        q.push({word, len + 1});
                        dict.erase(word);
                    }
                }
                word[i] = original_char;
            }
        }
        return 0;
    }
};

Example Problem Leetcode 126. 单词接龙 II

原理： 与 “单词接龙” 类似，但要求返回所有最短的转换序列。这需要对标准的BFS进行修改。

1. 双向BFS或单向BFS+记录路径：标准的BFS找到最短路径长度后就停止了，但我们需要所有路径。
2. 记录父节点：在BFS过程中，当从单词 u 找到一个新单词 v 时，我们将 u 记录为 v 的一个父节点。因为可能有多条最短路径到达 v，所以一个节点可以有多个父节点。
3. 分层遍历：BFS天然是分层的。我们必须确保只有在当前层完全遍历完之后，才将下一层的节点标记为已访问。这样可以保证我们找到的所有到 v 的路径都是最短的。
4. 回溯构建路径：BFS结束后，我们从 endWord 开始，使用记录的父节点关系，通过DFS回溯到 beginWord，从而构建出所有最短路径。

#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<std::string>> findLadders(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
        std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
        if (dict.find(endWord) == dict.end()) return {};

        std::unordered_map<std::string, std::vector<std::string>> parents;
        std::queue<std::string> q;
        q.push(beginWord);
        
        std::unordered_set<std::string> visited_this_level;
        visited_this_level.insert(beginWord);

        bool found = false;

        while (!q.empty()) {
            int level_size = q.size();
            for (int i = 0; i < level_size; ++i) {
                std::string word = q.front();
                q.pop();

                std::string original_word = word;
                for (int j = 0; j < word.length(); ++j) {
                    char original_char = word[j];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        word[j] = c;
                        if (dict.count(word)) {
                            if (word == endWord) found = true;
                            // Only add to queue if not visited in previous levels
                            if (dict.count(word)) { 
                                parents[word].push_back(original_word);
                                if (visited_this_level.find(word) == visited_this_level.end()) {
                                    q.push(word);
                                    visited_this_level.insert(word);
                                }
                            }
                        }
                    }
                    word[j] = original_char;
                }
            }
            // Remove visited words from dict for next levels
            for(const auto& w : visited_this_level) dict.erase(w);
            if (found) break;
        }

        std::vector<std::vector<std::string>> result;
        if (found) {
            std::vector<std::string> path = {endWord};
            buildPaths(endWord, beginWord, parents, path, result);
        }
        return result;
    }
private:
    void buildPaths(const std::string& word, const std::string& beginWord, 
                    const std::unordered_map<std::string, std::vector<std::string>>& parents, 
                    std::vector<std::string>& path, 
                    std::vector<std::vector<std::string>>& result) {
        if (word == beginWord) {
            std::vector<std::string> reversed_path = path;
            std::reverse(reversed_path.begin(), reversed_path.end());
            result.push_back(reversed_path);
            return;
        }
        if (parents.count(word)) {
            for (const std::string& p : parents.at(word)) {
                path.push_back(p);
                buildPaths(p, beginWord, parents, path, result);
                path.pop_back();
            }
        }
    }
};

Example Problem Leetcode 365. 水壶问题

原理： 判断是否可以用两个容量分别为 jug1Capacity 和 jug2Capacity 的水壶得到 targetCapacity 升水。

1. 数学解法（贝祖定理）：问题等价于问是否存在整数 x 和 y，使得 x * jug1 + y * jug2 = target。根据贝祖定理，这样的整数存在当且仅当 target 是 jug1 和 jug2 的最大公约数（GCD）的倍数。当然，target 也不能超过两个水壶的总容量。
2. 状态搜索解法（BFS）：可以将问题看作状态空间的搜索。每个状态是 (水量1, 水量2) 的一个元组。从初始状态 (0, 0) 开始，通过以下操作转移到新状态：
   • 倒空任一水壶。
   • 装满任一水壶。
   • 将一个水壶的水倒入另一个，直到一个倒空或另一个倒满。 使用BFS进行搜索，如果搜索到任何一个状态 (x, y) 使得 x + y = target，则返回 true。用一个 visited 集合来避免重复状态。

#include <numeric> // For std::gcd in C++17
#include <queue>
#include <unordered_set>

class Solution {
public:
    // Mathematical approach
    bool canMeasureWater(int jug1Capacity, int jug2Capacity, int targetCapacity) {
        if (jug1Capacity + jug2Capacity < targetCapacity) {
            return false;
        }
        if (jug1Capacity == 0 || jug2Capacity == 0) {
            return targetCapacity == 0 || jug1Capacity + jug2Capacity == targetCapacity;
        }
        return targetCapacity % std::gcd(jug1Capacity, jug2Capacity) == 0;
    }
    
    // BFS approach (for demonstration)
    bool canMeasureWaterBFS(int jug1, int jug2, int target) {
        if (target > jug1 + jug2) return false;
        
        std::queue<std::pair<int, int>> q;
        std::unordered_set<long long> visited;

        q.push({0, 0});
        visited.insert(0);

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();

            if (x == target || y == target || x + y == target) {
                return true;
            }

            std::vector<std::pair<int, int>> next_states;
            next_states.push_back({jug1, y}); // Fill jug1
            next_states.push_back({x, jug2}); // Fill jug2
            next_states.push_back({0, y});    // Empty jug1
            next_states.push_back({x, 0});    // Empty jug2
            // Pour jug1 to jug2
            int pour1to2 = std::min(x, jug2 - y);
            next_states.push_back({x - pour1to2, y + pour1to2});
            // Pour jug2 to jug1
            int pour2to1 = std::min(y, jug1 - x);
            next_states.push_back({x + pour2to1, y - pour2to1});

            for (auto const& state : next_states) {
                long long key = (long long)state.first * (jug2 + 1) + state.second;
                if (visited.find(key) == visited.end()) {
                    q.push(state);
                    visited.insert(key);
                }
            }
        }
        return false;
    }
};

Example Problem Leetcode 1971. 寻找图中是否存在路径

原理： 在给定的无向图中，判断从 source 到 destination 是否存在一条路径。这是一个基础的图连通性问题。

1. 构建邻接表：首先，根据 edges 数组构建图的邻接表表示，其中 graph[u] 存储所有与节点 u 相邻的节点。
2. BFS或DFS：
   • BFS：从 source 节点开始，将其加入队列。然后，逐层探索，将访问到的邻居加入队列。用一个 visited 数组记录已访问的节点。如果在探索过程中遇到了 destination，则说明路径存在。
   • DFS：从 source 节点开始递归。在递归函数中，访问当前节点，然后对其所有未访问的邻居进行递归调用。如果某次调用到达了 destination，则返回 true。

#include <vector>
#include <queue>

class Solution {
public:
    bool validPath(int n, std::vector<std::vector<int>>& edges, int source, int destination) {
        if (source == destination) return true;
        
        std::vector<std::vector<int>> graph(n);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        std::queue<int> q;
        q.push(source);
        std::vector<bool> visited(n, false);
        visited[source] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            if (u == destination) return true;

            for (int v : graph[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
        return false;
    }
};

Example Problem Leetcode 399. 除法求值

原理： 给定一系列变量除法等式，求解查询。我们可以将问题建模成一个图，变量是节点，a / b = k 表示从 a 到 b 的有向边权重为 k，从 b 到 a 的权重为 1/k。查询 c / d 就变成了寻找从 c 到 d 的路径，路径上所有权重的乘积就是答案。 对于每个查询，我们可以使用BFS（或DFS）在图上搜索路径。

#include <vector>
#include <string>
#include <unordered_map>
#include <queue>

class Solution {
public:
    std::vector<double> calcEquation(std::vector<std::vector<std::string>>& equations, std::vector<double>& values, std::vector<std::vector<std::string>>& queries) {
        std::unordered_map<std::string, std::vector<std::pair<std::string, double>>> graph;
        for (int i = 0; i < equations.size(); ++i) {
            graph[equations[i][0]].push_back({equations[i][1], values[i]});
            graph[equations[i][1]].push_back({equations[i][0], 1.0 / values[i]});
        }

        std::vector<double> results;
        for (const auto& q : queries) {
            results.push_back(bfs(q[0], q[1], graph));
        }
        return results;
    }
private:
    double bfs(const std::string& start, const std::string& end, std::unordered_map<std::string, std::vector<std::pair<std::string, double>>>& graph) {
        if (graph.find(start) == graph.end() || graph.find(end) == graph.end()) {
            return -1.0;
        }

        std::queue<std::pair<std::string, double>> q;
        q.push({start, 1.0});
        std::unordered_set<std::string> visited;
        visited.insert(start);

        while (!q.empty()) {
            auto [curr_node, curr_val] = q.front();
            q.pop();

            if (curr_node == end) return curr_val;

            for (const auto& neighbor : graph[curr_node]) {
                if (visited.find(neighbor.first) == visited.end()) {
                    visited.insert(neighbor.first);
                    q.push({neighbor.first, curr_val * neighbor.second});
                }
            }
        }
        return -1.0;
    }
};

记忆化搜索#

记忆化搜索是自顶向下动态规划的一种实现方式。它本质上是递归（DFS），但增加了一个缓存（如哈希表或数组）来存储已经计算过的子问题的解。当再次遇到相同的子问题时，直接从缓存中获取结果，从而避免重复计算。

Example Problem Leetcode 241. 为运算表达式设计优先级

原理： 给定一个包含数字和运算符的字符串，返回所有可能通过不同加括号方式计算出的结果。这是一个典型的分治问题，可以用递归解决。在 expression 的每个运算符位置，我们可以将其分为左右两部分，递归计算两部分所有可能的结果，然后将两边的结果根据当前运算符进行组合。由于子表达式会被重复计算，我们可以使用记忆化来优化。

#include <vector>
#include <string>
#include <unordered_map>

class Solution {
public:
    std::vector<int> diffWaysToCompute(std::string expression) {
        return dfs(expression);
    }
private:
    std::unordered_map<std::string, std::vector<int>> memo;

    std::vector<int> dfs(const std::string& expr) {
        if (memo.count(expr)) {
            return memo[expr];
        }

        std::vector<int> results;
        for (int i = 0; i < expr.length(); ++i) {
            char c = expr[i];
            if (c == '+' || c == '-' || c == '*') {
                std::vector<int> left = dfs(expr.substr(0, i));
                std::vector<int> right = dfs(expr.substr(i + 1));
                for (int l : left) {
                    for (int r : right) {
                        if (c == '+') results.push_back(l + r);
                        else if (c == '-') results.push_back(l - r);
                        else results.push_back(l * r);
                    }
                }
            }
        }

        if (results.empty()) { // Base case: the expression is a single number
            results.push_back(std::stoi(expr));
        }

        return memo[expr] = results;
    }
};

Example Problem Leetcode 488. 祖玛游戏

原理： 经典的状态压缩 + 记忆化搜索。目标是用最少的手中球消去所有桌上球。

• 状态：(board_state, hand_state)，即桌面球的布局和手中球的状况。board_state 是一个字符串，hand_state 也是一个字符串（或频率图）。
• 递归/DFS：定义一个函数 solve(board, hand) 返回消去当前 board 所需的最少球数。
  • 基准情况：如果 board 为空，返回0。如果 hand 为空但 board 不为空，返回无穷大。
  • 递归步骤：遍历 hand 中的每种颜色的球。对于每种球，尝试将其插入到 board 的每个可能位置（包括两个相同颜色球之间）。
  • 插入后，检查是否触发消除（连续三个或以上同色球）。如果触发，则递归处理消除后的新 board。
  • 取所有成功尝试中的最小值。
• 记忆化：使用 map<pair<string, string>, int> 或类似结构来缓存 (board, hand) 状态的结果，避免重复计算。

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

class Solution {
public:
    int findMinStep(std::string board, std::string hand) {
        std::unordered_map<char, int> hand_count;
        for (char c : hand) hand_count[c]++;
        
        memo.clear();
        int result = dfs(board, hand_count);
        return result > hand.length() ? -1 : result;
    }

private:
    std::unordered_map<std::string, int> memo;

    int dfs(std::string board, std::unordered_map<char, int>& hand) {
        if (board.empty()) return 0;
        
        std::string state_key = board + "#";
        for(auto const& [key, val] : hand) {
            state_key += std::to_string(key) + std::to_string(val);
        }
        if (memo.count(state_key)) return memo[state_key];

        int min_steps = 1e9;

        for (int i = 0; i <= board.length(); ++i) {
            for (auto const& [color, count] : hand) {
                if (count > 0) {
                    // Optimization: only insert if it can form a group of 3
                    // or if inserting between two same-colored balls.
                    if (i > 0 && i < board.length() && board[i-1] == board[i] && board[i-1] != color) continue;
                    if (i < board.length() && board[i] == color) {} // ok
                    else if (i > 0 && board[i-1] == color) {} // ok
                    else continue;


                    hand[color]--;
                    std::string new_board = board.substr(0, i) + color + board.substr(i);
                    
                    std::string cleaned_board = cleanup(new_board);
                    
                    int steps = dfs(cleaned_board, hand);
                    if (steps != 1e9) {
                        min_steps = std::min(min_steps, 1 + steps);
                    }
                    
                    hand[color]++; // backtrack
                }
            }
        }
        
        return memo[state_key] = min_steps;
    }

    std::string cleanup(std::string board) {
        int start = 0;
        while (start < board.length()) {
            int end = start;
            while (end < board.length() && board[end] == board[start]) {
                end++;
            }
            if (end - start >= 3) {
                board.erase(start, end - start);
                start = 0; // Restart scan
            } else {
                start = end;
            }
        }
        return board;
    }
};

Example Problem Leetcode 1444. 切披萨的方案数

原理： 动态规划/记忆化搜索。dp(r, c, k) 表示将 (r, c) 右下角的披萨切成 k 块（包含当前块）的方案数。

1. 预处理：为了快速判断任意一块披萨是否含有苹果，先预计算一个二维前缀和数组 apples[i][j]，表示从 (i, j) 到右下角 (rows-1, cols-1) 的苹果总数。
2. 状态：dp(r, c, k) - 将由 (r, c) 定义的右下角区域切成 k 块的方案数。
3. 递归/DFS：
   • 基准情况：如果 k=1，检查当前区域是否有苹果，有则返回1，否则返回0。如果当前区域苹果数小于 k，无法满足每块至少一个苹果，返回0。
   • 递归步骤：
     • 水平切割：遍历所有可能的水平切割线 nr (从 r+1 到 rows-1)。如果上半部分（从 r 到 nr-1）含有苹果，则方案数增加 dp(nr, c, k-1)。
     • 垂直切割：遍历所有可能的垂直切割线 nc (从 c+1 到 cols-1)。如果左半部分（从 c 到 nc-1）含有苹果，则方案数增加 dp(r, nc, k-1)。
4. 记忆化：使用三维数组 memo[r][c][k] 存储结果。

#include <vector>
#include <string>

class Solution {
public:
    int ways(std::vector<std::string>& pizza, int k) {
        int rows = pizza.size(), cols = pizza[0].size();
        apples.assign(rows + 1, std::vector<int>(cols + 1, 0));
        memo.assign(rows, std::vector<std::vector<int>>(cols, std::vector<int>(k + 1, -1)));
        
        for (int i = rows - 1; i >= 0; --i) {
            for (int j = cols - 1; j >= 0; --j) {
                apples[i][j] = (pizza[i][j] == 'A') + apples[i+1][j] + apples[i][j+1] - apples[i+1][j+1];
            }
        }
        
        return dfs(0, 0, k, rows, cols);
    }

private:
    std::vector<std::vector<int>> apples;
    std::vector<std::vector<std::vector<int>>> memo;
    int MOD = 1e9 + 7;

    int dfs(int r, int c, int k, int rows, int cols) {
        if (apples[r][c] == 0) return 0;
        if (k == 1) return 1;
        if (memo[r][c][k] != -1) return memo[r][c][k];

        long long ans = 0;
        // Horizontal cuts
        for (int nr = r + 1; nr < rows; ++nr) {
            if (apples[r][c] - apples[nr][c] > 0) { // Upper piece has apples
                ans = (ans + dfs(nr, c, k - 1, rows, cols)) % MOD;
            }
        }
        // Vertical cuts
        for (int nc = c + 1; nc < cols; ++nc) {
            if (apples[r][c] - apples[r][nc] > 0) { // Left piece has apples
                ans = (ans + dfs(r, nc, k - 1, rows, cols)) % MOD;
            }
        }
        return memo[r][c][k] = ans;
    }
};

Example Problem Leetcode 1387. 将整数按权重排序

原理： 计算每个整数的“权重”（变为1所需的步数），然后根据权重和原始值排序。计算权重的过程就是经典的“考拉兹猜想”问题。

• 权重计算：对于一个数 x，如果 x 是偶数，则 x = x / 2；如果 x 是奇数，则 x = 3 * x + 1。重复此过程直到 x=1，所用步数即为权重。
• 记忆化：在计算权重的过程中，很多数字的权重会被重复计算。例如，计算 7 的权重时会经过 22 -> 11 -> 34 -> 17...，之后计算 11 的权重时路径是重复的。我们可以用一个哈希表或数组 memo 来存储已计算过的数字的权重。
• 排序：计算出 [lo, hi] 区间内每个数的权重后，将 (权重, 数值) 对存起来，然后自定义排序规则进行排序。

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        std::vector<std::pair<int, int>> weighted_nums;
        for (int i = lo; i <= hi; ++i) {
            weighted_nums.push_back({getWeight(i), i});
        }
        
        std::sort(weighted_nums.begin(), weighted_nums.end());
        
        return weighted_nums[k - 1].second;
    }

private:
    std::unordered_map<int, int> memo;

    int getWeight(int n) {
        if (n == 1) return 0;
        if (memo.count(n)) return memo[n];
        
        if (n % 2 == 0) {
            return memo[n] = 1 + getWeight(n / 2);
        } else {
            return memo[n] = 1 + getWeight(3 * n + 1);
        }
    }
};

Example Problem Leetcode 224. 基本计算器

原理： 实现一个支持 +、- 和 () 的基本计算器。递归是处理括号嵌套的自然方法。

• 主循环：遍历字符串。
• 数字：解析完整的数字。
• 运算符：+ 或 -，更新符号 sign。
• (：遇到左括号，说明进入了一个新的子表达式。递归调用计算器函数来求解这个子表达式的值。递归调用会返回它处理完的表达式的结束位置，主循环从这个新位置继续。
• )：遇到右括号，说明当前子表达式计算结束，返回结果。
• 栈方法：也可以用栈来处理。遇到 ( 时，将当前的计算结果和符号 sign 入栈，然后重置结果和符号，开始计算括号内的新表达式。遇到 ) 时，将括号内的计算结果与栈顶的旧结果和符号合并。

#include <string>
#include <stack>

class Solution {
public:
    int calculate(std::string s) {
        std::stack<int> st;
        int result = 0;
        int sign = 1;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            if (isdigit(c)) {
                long num = 0;
                while (i < n && isdigit(s[i])) {
                    num = num * 10 + (s[i] - '0');
                    i++;
                }
                i--; // Decrement i because the outer loop increments it
                result += sign * num;
            } else if (c == '+') {
                sign = 1;
            } else if (c == '-') {
                sign = -1;
            } else if (c == '(') {
                st.push(result);
                st.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result *= st.top(); st.pop(); // sign
                result += st.top(); st.pop(); // previous result
            }
        }
        return result;
    }
};

Example Problem Leetcode 273. 整数转换英文表示

原理： 将一个非负整数转换为其英文表示。这是一个分治/递归问题。

1. 分解：数字可以按千位（“Thousand”）、百万位（“Million”）、十亿位（“Billion”）来分解。例如，1,234,567 可以看作 1 Million + 234 Thousand + 567。
2. 基本单元：我们需要一个辅助函数，能将任何小于1000的数转换为英文。
   • 这个函数可以进一步分解：处理百位（n / 100）、十位和个位。
   • 需要预定义 1-19 和 20, 30, ..., 90 的英文单词。
3. 递归/主逻辑：
   • 从最大的单位（Billion）开始处理。
   • 取 num / 1,000,000,000，递归调用转换函数处理这个部分，然后加上 “Billion”。
   • 对余数 num % 1,000,000,000 重复此过程，处理 “Million”，然后 “Thousand”，最后是小于1000的部分。

#include <string>
#include <vector>

class Solution {
private:
    std::vector<std::string> less_than_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    std::vector<std::string> tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    std::vector<std::string> thousands = {"", "Thousand", "Million", "Billion"};

public:
    std::string numberToWords(int num) {
        if (num == 0) return "Zero";
        
        std::string result = "";
        int i = 0;
        while (num > 0) {
            if (num % 1000 != 0) {
                result = helper(num % 1000) + thousands[i] + " " + result;
            }
            num /= 1000;
            i++;
        }
        
        // Trim trailing space
        size_t endpos = result.find_last_not_of(" ");
        if (std::string::npos != endpos) {
            result = result.substr(0, endpos + 1);
        }
        return result;
    }

private:
    std::string helper(int n) {
        if (n == 0) return "";
        if (n < 20) {
            return less_than_20[n] + " ";
        }
        if (n < 100) {
            return tens[n / 10] + " " + helper(n % 10);
        }
        return less_than_20[n / 100] + " Hundred " + helper(n % 100);
    }
};

Example Problem Leetcode 10. 正则表达式匹配

原理： 实现一个支持 . 和 * 的正则表达式匹配。* 表示前面的元素可以出现零次或多次。

1. 递归定义：
   • 如果模式串 p 为空，文本串 s 也为空，返回真。
   • 如果模式串 p 为空，文本串 s 不为空，返回假。
   • 如果模式串 p 的下一个字符不是 *：
     • 如果文本串 s 为空，返回假。
     • 如果模式串 p 的第一个字符和文本串 s 的第一个字符匹配，则继续递归匹配剩余部分。
   • 如果模式串 p 的下一个字符是 *：
     • 尝试两种情况：
       1. 将 * 看作是零个前面元素的匹配，直接跳过 * 和它前面的元素。
       2. 如果文本串 s 的第一个字符和模式串 p 的第一个字符匹配，则将 * 看作是一个或多个前面元素的匹配，文本串 s 向后移动一个字符，模式串 p 保持不变（因为 * 可以匹配多个）。

#include <string>

class Solution {
public:
    bool isMatch(std::string s, std::string p) {
        return dfs(s, p, 0, 0);
    }
private:
    bool dfs(const std::string& s, const std::string& p, int i, int j) {
        if (j == p.size()) return i == s.size();
        
        bool match = (i < s.size() && (s[i] == p[j] || p[j] == '.'));

        if (j + 1 < p.size() && p[j + 1] == '*') {
            return dfs(s, p, i, j + 2) || (match && dfs(s, p, i + 1, j));
        } else {
            return match && dfs(s, p, i + 1, j + 1);
        }
    }
};

Example Problem Leetcode 91. 解码方法

原理： 给定一个只包含数字的字符串，计算有多少种不同的解码方法。每个数字可以单独解码，也可以与下一个数字组合解码（前提是组合后的数字不超过26）。

1. 状态定义：dp[i] 表示前 i 个字符的解码方法总数。
2. 状态转移：
   • 如果第 i 个字符不为 0，则 dp[i] += dp[i-1]。
   • 如果第 i-1 和第 i 个字符组合成的数字在 10 到 26 之间，则 dp[i] += dp[i-2]。
3. 初始值：dp[0] = 1（空字符串），dp[1] 根据第一个字符决定（如果不为 0，则为 1）。

#include <string>
#include <vector>

class Solution {
public:
    int numDecodings(std::string s) {
        if (s.empty() || s[0] == '0') return 0;
        
        int n = s.size();
        std::vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i) {
            if (s[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            int two_digit = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
            if (two_digit >= 10 && two_digit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
};

Example Problem Leetcode 139. 单词拆分

原理： 给定一个字符串和一个词典，判断字符串是否可以被拆分为若干个在词典中出现的单词。

1. 状态定义：dp[i] 表示前 i 个字符是否可以被拆分。
2. 状态转移：
   • 初始化 dp[0] = true。
   • 对于每个 i，检查所有可能的 j（0 <= j < i），如果 dp[j] 为真且 s[j:i] 在词典中，则 dp[i] 为真。
3. 优化：可以用一个哈希集合存词典，以便快速查找。

#include <string>
#include <vector>
#include <unordered_set>

class Solution {
public:
    bool wordBreak(std::string s, std::unordered_set<std::string>& wordDict) {
        int n = s.size();
        std::vector<bool> dp(n + 1, false);
        dp[0] = true;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordDict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

Example Problem Leetcode 5. 最长回文子串

原理： 寻找给定字符串中的最长回文子串。回文串是正着读和反着读都一样的字符串。

1. 状态定义：dp[i][j] 表示子串 s[i...j] 是否是回文。
2. 状态转移：
   • 初始化：所有长度为1的子串都是回文，dp[i][i] = true。
   • 对于长度为2的子串，dp[i][i+1] = (s[i] == s[i+1])。
   • 对于长度大于2的子串，dp[i][j] = (s[i] == s[j] && dp[i+1][j-1])。
3. 结果：遍历所有 dp[i][j]，找到最长的回文子串。

#include <string>
#include <vector>

class Solution {
public:
    std::string longestPalindrome(std::string s) {
        int n = s.size();
        if (n == 0) return "";
        
        std::vector<std::vector<bool>> dp(n, std::vector<bool>(n, false));
        int max_len = 1, start = 0;

        // All substrings of length 1 are palindromic
        for (int i = 0; i < n; ++i) {
            dp[i][i] = true;
        }

        // Check for substrings of length 2
        for (int i = 0; i < n - 1; ++i) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                start = i;
                max_len = 2;
            }
        }

        // Check for substrings of length > 2
        for (int len = 3; len <= n; ++len) {
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    start = i;
                    max_len = len;
                }
            }
        }

        return s.substr(start, max_len);
    }
};

Example Problem Leetcode 32. 最长有效括号

原理： 寻找字符串中最长的有效括号子串。有效括号指的是每个左括号都有对应的右括号，并且左右括号的顺序正确。

1. 状态定义：dp[i] 表示以 s[i] 结尾的最长有效括号子串的长度。
2. 状态转移：
   • 初始化 dp[0] = 0。
   • 遍历字符串，对于每个 )：
     • 如果前一个字符是 (，则 dp[i] = dp[i-2] + 2。
     • 如果前一个字符是 )，则需要找到与之匹配的左括号，更新 dp[i]。
3. 结果：dp 数组中的最大值即为结果。

#include <string>
#include <vector>
#include <stack>

class Solution {
public:
    int longestValidParentheses(std::string s) {
        int max_len = 0;
        std::vector<int> dp(s.size(), 0);
        
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
            }
            max_len = std::max(max_len, dp[i]);
        }
        
        return max_len;
    }
};

Example Problem Leetcode 300. 最长递增子序列

原理： 在一个无序数组中找到一个最长的递增子序列。该问题可以通过动态规划解决。

1. 状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。
2. 状态转移：
   • 初始化 dp[i] = 1。
   • 对于每个 i，检查所有小于 i 的 j，如果 nums[j] < nums[i]，则更新 dp[i]。
3. 结果：dp 数组中的最大值即为结果。

#include <vector>
#include <algorithm>

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::vector<int> dp(nums.size(), 1);
        int max_length = 1;

        for (int i = 1; i < nums.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = std::max(dp[i], dp[j] + 1);
                }
            }
            max_length = std::max(max_length, dp[i]);
        }
        return max_length;
    }
};

Example Problem Leetcode 674. 最长连续递增序列

原理： 寻找数组中最长的连续递增子序列。与最长递增子序列不同的是，这里要求是连续的。

1. 状态定义：dp[i] 表示以 nums[i] 结尾的最长连续递增子序列的长度。
2. 状态转移：
   • 初始化 dp[0] = 1。
   • 对于每个 i，如果 nums[i] > nums[i-1]，则 dp[i] = dp[i-1] + 1。
3. 结果：dp 数组中的最大值即为结果。

#include <vector>
#include <algorithm>

class Solution {
public:
    int findLengthOfLCIS(std::vector<int>& nums) {
        if (nums.empty()) return 0;
        
        std::vector<int> dp(nums.size(), 1);
        int max_length = 1;

        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            max_length = std::max(max_length, dp[i]);
        }
        return max_length;
    }
};

Example Problem Leetcode 53. 最大子数组和

原理： 寻找数组中和最大的连续子数组。暴力解法是合并数组后找中点，但时间复杂度不满足要求。分治法的思路是寻找一个合适的分割线，将两个数组都分成左右两部分，使得 左半部分所有元素 <= 右半部分所有元素，并且 左半部分元素个数 = 右半部分元素个数（或多一个）。这可以转化为在较短的数组中二分查找这个分割线的位置。

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        return maxSubArrayDivideConquer(nums, 0, nums.size() - 1);
    }
private:
    int maxSubArrayDivideConquer(const std::vector<int>& nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = left + (right - left) / 2;
        
        int left_max = maxSubArrayDivideConquer(nums, left, mid);
        int right_max = maxSubArrayDivideConquer(nums, mid + 1, right);
        int cross_max = maxCrossingSum(nums, left, mid, right);
        
        return std::max({left_max, right_max, cross_max});
    }

    int maxCrossingSum(const std::vector<int>& nums, int left, int mid, int right) {
        int left_sum = INT_MIN;
        int sum = 0;
        for (int i = mid; i >= left; --i) {
            sum += nums[i];
            if (sum > left_sum) {
                left_sum = sum;
            }
        }
        
        int right_sum = INT_MIN;
        sum = 0;
        for (int i = mid + 1; i <= right; ++i) {
            sum += nums[i];
            if (sum > right_sum) {
                right_sum = sum;
            }
        }
        return left_sum + right_sum;
    }
};

Example Problem Leetcode 2407. 最长递增子序列 II

原理： 寻找最长递增子序列，但要求相邻元素之差不超过 k。这是一个动态规划问题，但由于数据范围，需要使用数据结构进行优化。线段树是实现这种优化的有效工具，其本身就蕴含了分治的思想。

• DP状态：dp[v] 表示以数值 v 结尾的满足条件的最长子序列的长度。
• 状态转移：当我们处理一个新的数 num 时，我们需要找到在 [num - k, num - 1] 这个数值范围内的所有数 v 中，dp[v] 的最大值，记为 max_prev_len。那么，以 num 结尾的子序列长度就是 max_prev_len + 1。
• 线段树优化：线段树用于维护数值范围上的 dp 值。
  1. 查询：对于每个 num，在线段树中查询范围 [num - k, num - 1] 的最大值。
  2. 更新：计算出 dp[num] 后，在线段树中更新 num 位置的值。

#include <vector>
#include <algorithm>

// Segment Tree Node
struct Node {
    int max_val;
};

class SegTree {
public:
    SegTree(int size) : n(size), tree(4 * size, {0}) {}

    void update(int index, int val) {
        update_recursive(1, 0, n - 1, index, val);
    }

    int query(int l, int r) {
        return query_recursive(1, 0, n - 1, l, r);
    }

private:
    int n;
    std::vector<Node> tree;

    void update_recursive(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node].max_val = val;
            return;
        }
        int mid = (start + end) / 2;
        if (start <= idx && idx <= mid) {
            update_recursive(2 * node, start, mid, idx, val);
        } else {
            update_recursive(2 * node + 1, mid + 1, end, idx, val);
        }
        tree[node].max_val = std::max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
    }

    int query_recursive(int node, int start, int end, int l, int r) {
        if (r < start || end < l || l > r) {
            return 0;
        }
        if (l <= start && end <= r) {
            return tree[node].max_val;
        }
        int mid = (start + end) / 2;
        int p1 = query_recursive(2 * node, start, mid, l, r);
        int p2 = query_recursive(2 * node + 1, mid + 1, end, l, r);
        return std::max(p1, p2);
    }
};

class Solution {
public:
    int lengthOfLIS(std::vector<int>& nums, int k) {
        int max_val = 0;
        for(int num : nums) max_val = std::max(max_val, num);

        SegTree st(max_val + 1);
        int max_len = 0;

        for (int num : nums) {
            int prev_max_len = st.query(std::max(0, num - k), num - 1);
            int current_len = prev_max_len + 1;
            st.update(num, current_len);
            max_len = std::max(max_len, current_len);
        }
        return max_len;
    }
};

回溯 (Backtracking)#

回溯是一种试探性算法，用于寻找所有（或某个）解。它通过构建解的所有可能的候选者，并逐步验证每个候选者是否满足问题的要求。 回溯法通常用于解决组合、排列、子集等问题。其基本思想是：对问题的解空间进行深度优先搜索（DFS），在搜索过程中根据当前解的状态，动态地决定是否继续向下搜索，还是进行回溯。

Example Problem Leetcode 22. 括号生成

原理： 生成所有有效的括号组合。使用回溯法，维护一个当前组合的字符串 current，以及左右括号的剩余可用数量 left 和 right。

1. 基准情况：当 current 长度达到 2 * n 时，说明生成了一个完整的组合，加入结果集中。
2. 递归步骤：
   • 如果 left > 0，说明还有左括号可以使用，尝试添加一个左括号，并递归。
   • 如果 right > left，说明当前的左括号数量少于右括号，可以添加右括号，保持组合的有效性，然后递归。

#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> generateParenthesis(int n) {
        std::vector<std::string> result;
        std::string current;
        backtrack(result, current, n, n);
        return result;
    }
private:
    void backtrack(std::vector<std::string>& result, std::string& current, int left, int right) {
        if (current.length() == 2 * left) {
            result.push_back(current);
            return;
        }
        if (left > 0) {
            current.push_back('(');
            backtrack(result, current, left - 1, right);
            current.pop_back();
        }
        if (right > left) {
            current.push_back(')');
            backtrack(result, current, left, right - 1);
            current.pop_back();
        }
    }
};

Example Problem Leetcode 46. 全排列

原理： 生成数组的所有排列。使用回溯法，维护一个当前排列的数组 current，以及一个布尔数组 used 来标记数组元素是否被使用。

1. 基准情况：当 current 长度达到 nums 长度时，说明生成了一个完整的排列，加入结果集中。
2. 递归步骤：
   • 遍历 nums 中的每个元素，如果未被使用，则将其加入 current，并标记为已使用。
   • 递归调用以生成下一个位置的排列。
   • 回溯时，撤销当前选择，标记为未使用。

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        std::vector<bool> used(nums.size(), false);
        backtrack(result, current, nums, used);
        return result;
    }
private:
    void backtrack(std::vector<std::vector<int>>& result, std::vector<int>& current, 
                   const std::vector<int>& nums, std::vector<bool>& used) {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            used[i] = true;
            current.push_back(nums[i]);
            backtrack(result, current, nums, used);
            current.pop_back();
            used[i] = false;
        }
    }
};

Example Problem Leetcode 17. 电话号码的字母组合

原理： 给定一个电话号码的数字，返回所有可能的字母组合。每个数字对应的字母由一个映射表给出。

1. 基准情况：当 index 等于数字字符串长度时，说明生成了一组完整的字母组合，加入结果集中。
2. 递归步骤：
   • 获取当前数字对应的所有字母。
   • 遍历这些字母，将每个字母加入当前组合。
   • 递归调用以生成下一个数字的字母组合。
   • 回溯时，撤销当前字母选择。

#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> letterCombinations(std::string digits) {
        std::vector<std::string> result;
        if (digits.empty()) return result;
        std::string current;
        backtrack(result, current, digits, 0);
        return result;
    }
private:
    void backtrack(std::vector<std::string>& result, std::string& current, 
                   const std::string& digits, int index) {
        if (index == digits.length()) {
            result.push_back(current);
            return;
        }
        std::string letters = getLetters(digits[index]);
        for (char c : letters) {
            current.push_back(c);
            backtrack(result, current, digits, index + 1);
            current.pop_back();
        }
    }

    std::string getLetters(char digit) {
        switch (digit) {
            case '2': return "abc";
            case '3': return "def";
            case '4': return "ghi";
            case '5': return "jkl";
            case '6': return "mno";
            case '7': return "pqrs";
            case '8': return "tuv";
            case '9': return "wxyz";
            default: return "";
        }
    }
};

Example Problem Leetcode 51. N 皇后

原理： 在 n * n 的棋盘上放置 n 个皇后，使其互不攻击。皇后可以攻击同一行、同一列或同一对角线上的任意棋子。

1. 基准情况：当 row 等于 n 时，说明成功放置了 n 个皇后，将当前棋盘布局加入结果集中。
2. 递归步骤：
   • 遍历棋盘的每一列，尝试在当前行的每一列放置皇后。
   • 检查该位置是否安全（即该列和两个对角线没有其他皇后）。
   • 如果安全，则在该位置放置皇后，并递归调用以放置下一行的皇后。
   • 回溯时，撤销当前皇后放置。

#include <vector>

class Solution {
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<std::string>> result;
        std::vector<std::string> board(n, std::string(n, '.'));
        backtrack(result, board, 0, n);
        return result;
    }
private:
    void backtrack(std::vector<std::vector<std::string>>& result, std::vector<std::string>& board, 
                   int row, int n) {
        if (row == n) {
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (!isSafe(board, row, col, n)) {
                continue;
            }
            board[row][col] = 'Q';
            backtrack(result, board, row + 1, n);
            board[row][col] = '.';
        }
    }

    bool isSafe(const std::vector<std::string>& board, int row, int col, int n) {
        for (int i = 0; i < row; ++i) {
            if (board[i][col] == 'Q') {
                return false;
            }
            int diag1 = col - (row - i);
            int diag2 = col + (row - i);
            if (diag1 >= 0 && board[i][diag1] == 'Q') {
                return false;
            }
            if (diag2 < n && board[i][diag2] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

Example Problem Leetcode 52. N 皇后 II

原理： 与 “N 皇后” 问题完全相同，只是最后不要求返回棋盘布局，而是返回解的总数。因此，我们可以在回溯算法的基准情况（当 row == n）中，不存储棋盘，而是简单地将计数器加一。

#include <vector>

class Solution {
public:
    int totalNQueens(int n) {
        int count = 0;
        std::vector<bool> cols(n, false);
        std::vector<bool> diag1(2 * n - 1, false);
        std::vector<bool> diag2(2 * n - 1, false);
        backtrack(0, n, count, cols, diag1, diag2);
        return count;
    }
private:
    void backtrack(int row, int n, int& count,
                   std::vector<bool>& cols, std::vector<bool>& diag1, std::vector<bool>& diag2) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; ++col) {
            int d1 = row - col + n - 1;
            int d2 = row + col;
            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue;
            }
            cols[col] = diag1[d1] = diag2[d2] = true;
            backtrack(row + 1, n, count, cols, diag1, diag2);
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
};

Example Problem Leetcode 47. 全排列 II

原理： 生成包含重复元素数组的全排列。为了避免生成重复的排列，我们需要在回溯时进行剪枝。

1. 排序：首先对输入数组 nums 进行排序。这使得相同的元素相邻，便于剪枝。
2. 剪枝：在回溯的循环中，如果 i > start 并且 nums[i] == nums[i-1]，则跳过 nums[i]，以避免产生重复的排列。
3. used 数组：需要一个 used 布尔数组来跟踪每个索引的元素是否已在当前路径中使用。

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        std::vector<bool> used(nums.size(), false);
        std::sort(nums.begin(), nums.end());
        backtrack(nums, path, used, result);
        return result;
    }
private:
    void backtrack(const std::vector<int>& nums, std::vector<int>& path, std::vector<bool>& used, std::vector<std::vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            // Pruning: if current element is same as previous, and previous was not used in this path, skip.
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, path, used, result);
            path.pop_back();
            used[i] = false;
        }
    }
};

Example Problem Leetcode 39. 组合总和

原理： 从一个无重复元素的数组中找出所有和为 target 的组合，每个数字可以使用无限次。

1. 排序：对 candidates 排序可以进行一个优化剪枝：如果当前和已经大于 target，后续更大的元素也不可能满足条件。
2. 回溯：定义 backtrack(start, current_sum, path)。
   • start 参数用于避免产生重复的组合（如 [2,3] 和 [3,2]）。在递归调用时，我们只从 start 索引开始选择，而不是从0开始。
   • 如果 current_sum == target，找到一个解。
   • 如果 current_sum > target，剪枝。
   • 循环从 start 到数组末尾，选择一个 candidates[i]，加入路径，递归调用 backtrack(i, ...)（注意是 i 而不是 i+1，因为数字可以重复使用）。然后回溯。

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        std::sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, path, result);
        return result;
    }
private:
    void backtrack(const std::vector<int>& candidates, int remain, int start, std::vector<int>& path, std::vector<std::vector<int>>& result) {
        if (remain == 0) {
            result.push_back(path);
            return;
        }
        if (remain < 0) {
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            path.push_back(candidates[i]);
            backtrack(candidates, remain - candidates[i], i, path, result);
            path.pop_back();
        }
    }
};

Example Problem Leetcode 40. 组合总和 II

原理： 与 “组合总和” 类似，但 candidates 可能包含重复数字，且每个数字只能使用一次。

1. 排序：必须排序以处理重复。
2. 回溯与剪枝：在回溯的循环中，如果 i > start 且 candidates[i] == candidates[i-1]，则跳过 candidates[i]，以避免产生重复的组合。

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        std::sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, path, result);
        return result;
    }
private:
    void backtrack(const std::vector<int>& candidates, int remain, int start, std::vector<int>& path, std::vector<std::vector<int>>& result) {
        if (remain == 0) {
            result.push_back(path);
            return;
        }
        if (remain < 0) return;

        for (int i = start; i < candidates.size(); ++i) {
            if (i > start && candidates[i] == candidates[i-1]) continue; // Skip duplicates
            
            path.push_back(candidates[i]);
            backtrack(candidates, remain - candidates[i], i + 1, path, result);
            path.pop_back();
        }
    }
};

Example Problem Leetcode 78. 子集

原理： 生成一个不含重复元素数组的所有子集（幂集）。 回溯法非常直观：对于数组中的每个元素，我们都有两种选择：将它包含在当前子集中，或者不包含。

#include <vector>

class Solution {
public:
    std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> path;
        backtrack(nums, 0, path, result);
        return result;
    }
private:
    void backtrack(const std::vector<int>& nums, int start, std::vector<int>& path, std::vector<std::vector<int>>& result) {
        result.push_back(path); // Add the current combination
        for (int i = start; i < nums.size(); ++i) {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.pop_back();
        }
    }
};