递归/回溯

1、没有重复项数字的全排列

1.1、问题描述

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. （以数字在数组中的位置靠前为优先级，按字典序排列输出。）

示例1

输入：[1,2,3]

返回值：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例2

输入：[1]

返回值：[[1]]

1.2、思路及代码

思路：

1. 我们创建一个函数 backtrack，它将生成排列并将它们存储在 result 中。
2. 函数 backtrack 接受四个参数：
   1. result：一个二维向量，用于存储所有生成的排列。
   2. permutation：一个向量，表示当前正在生成的排列。
   3. nums：给定的一组数字。
   4. used：一个布尔向量，用于标记数字是否已经被使用在当前排列中。
3. 在 backtrack 函数中，我们首先检查排列的长度是否等于给定数字的数量，如果是，说明当前排列已经完成，将其加入 result 中。
4. 然后，我们遍历给定数字数组 nums，对于每个数字，检查它是否已经在当前排列中使用（由 used 数组标记）。
5. 如果数字尚未使用，我们将其添加到当前排列中，将其标记为已使用，然后递归调用 backtrack 以生成下一个数字的排列。
6. 在递归返回后，我们进行回溯，将数字标记为未使用，并从排列中移除，以便生成其他排列。
7. 最终，将生成的所有排列存储在 result 中并返回。

参考代码：

#include <iostream>
#include <vector>

void backtrack(std::vector<std::vector<int>>& result, std::vector<int>& permutation, std::vector<int>& nums, std::vector<bool>& used) {
    // 如果排列的长度等于数字的数量，说明当前排列已经完成
    if (permutation.size() == nums.size()) {
        result.push_back(permutation);  // 将当前排列加入结果集
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) {
            continue;  // 数字已经在排列中，跳过
        }

        permutation.push_back(nums[i]);  // 将数字加入当前排列
        used[i] = true;  // 标记数字为已使用
        backtrack(result, permutation, nums, used);  // 递归生成下一个数字的排列
        used[i] = false;  // 回溯，将数字标记为未使用
        permutation.pop_back();  // 回溯，将数字从排列中移除
    }
}

std::vector<std::vector<int>> permute(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    std::vector<int> permutation;
    std::vector<bool> used(nums.size(), false);  // 用于标记数字是否已使用
    backtrack(result, permutation, nums, used);  // 从空排列开始生成所有排列
    return result;
}

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<std::vector<int>> result = permute(nums);

    std::cout << "给定数字的所有排列如下：" << std::endl;
    for (const auto& permutation : result) {
        std::cout << "[";
        for (int i = 0; i < permutation.size(); i++) {
            std::cout << permutation[i];
            if (i < permutation.size() - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "]" << std::endl;
    }

    return 0;
}

2、有重复项数字的全排列

2.1、问题描述

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

示例1

输入：[1,1,2]

返回值：[[1,1,2],[1,2,1],[2,1,1]]

示例2

输入：[0,1]

返回值：[[0,1],[1,0]]

2.2、思路及代码

思路：

1. 首先，需要明确如何处理可能的重复元素。为了避免生成重复的排列，我们可以在生成排列的过程中跳过相同的元素，只处理第一个出现的元素。这样可以避免生成重复排列。
2. 我们使用回溯算法来生成排列，回溯是一种递归的方法，用于尝试所有可能的排列组合。
3. 我们创建一个函数 backtrack，它将生成排列并将它们存储在 result 中。
4. 函数 backtrack 接受四个参数：
   1. result：一个二维向量，用于存储所有生成的排列。
   2. permutation：一个向量，表示当前正在生成的排列。
   3. nums：给定的一组数字。
   4. used：一个布尔向量，用于标记数字是否已经被使用在当前排列中。
5. 在 backtrack 函数中，我们首先检查排列的长度是否等于给定数字的数量，如果是，说明当前排列已经完成，将其加入 result 中。
6. 然后，我们遍历给定数字数组 nums，对于每个数字，检查它是否已经在当前排列中使用（由 used 数组标记）。
7. 如果数字尚未使用，我们将其添加到当前排列中，将其标记为已使用，然后递归调用 backtrack 以生成下一个数字的排列。
8. 在递归返回后，我们进行回溯，将数字标记为未使用，并从排列中移除，以便生成其他排列。
9. 最终，将生成的所有排列存储在 result 中并返回。

参考代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义回溯函数，用于生成排列
void backtrack(vector<vector<int>>& result, vector<int>& permutation, vector<int>& nums, vector<bool>& used) {
    if (permutation.size() == nums.size()) { // 如果当前排列长度等于数组长度，说明排列已完成
        result.push_back(permutation); // 将当前排列加入结果集
        return;
    }

    for (int i = 0; i < nums.size(); i++) { // 遍历数组中的每个数字
        if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
            // 如果数字已被使用，或者是相同数字的第二次使用，跳过
            continue;
        }
        used[i] = true; // 标记当前数字已被使用
        permutation.push_back(nums[i]); // 将当前数字添加到排列中
        backtrack(result, permutation, nums, used); // 递归生成下一个数字的排列
        used[i] = false; // 回溯，标记当前数字未被使用
        permutation.pop_back(); // 移除当前数字以生成其他排列
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> result; // 存储所有排列的结果集
    vector<int> permutation; // 当前正在生成的排列
    vector<bool> used(nums.size(), false); // 标记数字是否已被使用

    sort(nums.begin(), nums.end()); // 对输入数组排序，为了跳过重复元素

    backtrack(result, permutation, nums, used); // 调用回溯函数生成排列

    return result; // 返回结果集
}

int main() {
    vector<int> nums = {1, 1, 2};
    vector<vector<int>> result = permuteUnique(nums);

    cout << "所有排列如下：" << endl;
    for (const vector<int>& perm : result) {
        cout << "[ ";
        for (int num : perm) {
            cout << num << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}

3、岛屿数量

3.1、问题描述

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

例如：

输入

[

[1,1,0,0,0],

[0,1,0,1,1],

[0,0,0,1,1],

[0,0,0,0,0],

[0,0,1,1,1]

]

对应的输出为3

(注：存储的01数据其实是字符'0','1')

示例1

输入：[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]

返回值：3

示例2

输入：[[0]]

返回值：0

示例3

输入：[[1,1],[1,1]]

返回值：1

3.2、思路及代码

思路：

1. 遍历整个01矩阵，以查找陆地的起点：
   1. 初始化岛屿数量为0。
   2. 遍历矩阵的每个位置，从左上角开始，逐行逐列。如果当前位置的值为'1'，表示发现了陆地。
2. 一旦发现陆地，就从该位置开始进行深度优先搜索（DFS）：
   1. 递增岛屿数量，表示找到了一个新的岛屿。
   2. 使用DFS来遍历与当前位置相连的所有陆地，将它们标记为已访问。
   3. DFS递归地访问上下左右四个方向的相邻位置，如果相邻位置也是陆地，继续对它进行DFS。
   4. 在DFS过程中，将已访问的陆地标记为'0'，以避免重复计数。
3. 返回岛屿数量：
   1. 当DFS完成后，岛屿数量即为结果。每次找到一个新的陆地，都会增加岛屿数量。
   2. 重复步骤1和步骤2，以查找矩阵中的所有岛屿。
4. 最终得到岛屿的数量，即为答案

参考代码：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0; // 如果矩阵为空，返回0
        }

        int numIslands = 0; // 岛屿数量
        int rows = grid.size(); // 矩阵的行数
        int cols = grid[0].size(); // 矩阵的列数

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') { // 当前位置是陆地
                    numIslands++; // 新的岛屿开始
                    dfs(grid, i, j); // 深度优先搜索，将当前岛屿标记为已访问
                }
            }
        }

        return numIslands;
    }

private:
    void dfs(vector<vector<char>>& grid, int row, int col) {
        int rows = grid.size();
        int cols = grid[0].size();

        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
            return; // 超出矩阵范围或者当前位置是海洋，结束搜索
        }

        grid[row][col] = '0'; // 将当前位置标记为已访问

        // 继续搜索当前位置的上下左右相邻位置
        dfs(grid, row - 1, col); // 上
        dfs(grid, row + 1, col); // 下
        dfs(grid, row, col - 1); // 左
        dfs(grid, row, col + 1); // 右
    }
};

int main() {
    vector<vector<char>> grid = {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };

    Solution solution;
    int numIslands = solution.numIslands(grid);

    cout << "岛屿的数量：" << numIslands << endl;

    return 0;
}

4、字符串的排列

4.1、问题描述

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

**输入描述：**输入一个字符串,长度不超过10,字符只包括大小写字母。

示例1

输入："ab"

返回值：["ab","ba"]

说明：返回["ba","ab"]也是正确的

示例2

输入："aab"

返回值：["aab","aba","baa"]

示例3

输入："abc"

返回值：["abc","acb","bac","bca","cab","cba"]

示例4

输入：""

返回值：[""]

4.2、思路及代码

思路：

1. 创建一个递归函数，该函数用于生成字符串的排列。
2. 在每一轮递归中，我们将字符串划分为两部分：第一个字符和其余字符。
3. 对于第一个字符，我们将其与其余字符中的每个字符交换，并将其余字符视为新的字符串，进行递归。
4. 递归终止条件是：当字符串长度为1时，即字符串中只剩下一个字符时，无需再排列，将其添加到结果中。

参考代码：

#include <iostream>
#include <vector>
#include <string>

void permute(std::string& str, int startIndex, std::vector<std::string>& result) {
    if (startIndex == str.length() - 1) {
        result.push_back(str);  // 递归终止条件：将排列好的字符串添加到结果中
    } else {
        for (int i = startIndex; i < str.length(); i++) {
            // 交换第一个字符与当前字符
            std::swap(str[startIndex], str[i]);
            
            // 递归生成排列
            permute(str, startIndex + 1, result);
            
            // 恢复原始状态，以便下一次交换
            std::swap(str[startIndex], str[i]);
        }
    }
}

std::vector<std::string> generatePermutations(std::string str) {
    std::vector<std::string> result;
    if (str.empty()) {
        return result;
    }
    
    permute(str, 0, result);  // 调用排列生成函数
    
    return result;
}

int main() {
    std::string input = "ABC";
    std::vector<std::string> permutations = generatePermutations(input);
    
    std::cout << "字符串的全排列：" << std::endl;
    for (const std::string& perm : permutations) {
        std::cout << perm << std::endl;
    }
    
    return 0;
}

5、N皇后问题

5.1、问题描述

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后， 要求：任何两个皇后不同行，不同列也不在同一条斜线上， 求给一个整数 n ，返回 n 皇后的摆法数。

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

示例1

输入：1

返回值：1

示例2

输入：8

返回值：92

5.2、思路及代码

思路：

1. 创建一个长度为 n 的一维数组 queens，表示每一行的皇后所在的列数。
2. 从第一行开始，尝试放置皇后。
3. 对于每一行，从第一列开始，逐一尝试将皇后放置在某一列。
4. 在放置之前，检查该位置是否符合 N 皇后问题的规则：不在同一列，不在同一对角线上。
5. 如果符合规则，将皇后放置在该位置，然后递归处理下一行。
6. 如果无法放置皇后在当前行的任何列上，回溯到上一行，继续尝试其他列。
7. 重复这个过程，直到处理完所有行。
8. 每当成功放置皇后在最后一行，即完成了一种合法的 N 皇后摆放方式，将计数器加一。
9. 返回计数器的值，即为合法的摆放方式数。

参考代码：

#include <iostream>
#include <vector>

class NQueens {
public:
    int totalNQueens(int n) {
        std::vector<int> queens(n, -1);  // 初始化一个长度为 n 的数组，-1 表示尚未放置皇后
        int count = 0;  // 用于计数合法的摆放方式数量
        solveNQueens(queens, 0, count);  // 从第一行开始摆放皇后
        return count;
    }

private:
    void solveNQueens(std::vector<int>& queens, int row, int& count) {
        int n = queens.size();
        if (row == n) {
            count++;  // 找到了一种合法的摆放方式
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(queens, row, col)) {
                queens[row] = col;  // 放置皇后
                solveNQueens(queens, row + 1, count);  // 递归处理下一行
                queens[row] = -1;  // 回溯，恢复状态
            }
        }
    }

    bool isValid(const std::vector<int>& queens, int row, int col) {
        for (int i = 0; i < row; i++) {
            if (queens[i] == col ||  // 同一列有皇后
                queens[i] - i == col - row ||  // 主对角线有皇后
                queens[i] + i == col + row) {  // 副对角线有皇后
                return false;
            }
        }
        return true;
    }
};

int main() {
    NQueens nQueens;
    int n = 4;
    int solutions = nQueens.totalNQueens(n);
    
    std::cout << n << " 皇后问题的合法摆放方式数量为: " << solutions << std::endl;
    
    return 0;
}

6、括号生成

6.1、问题描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

"((()))", "(()())", "(())()", "()()()", "()(())"

示例1

输入：1

返回值：["()"]

示例2

输入：2

返回值：["(())","()()"]

6.2、思路及代码

思路：

1. 创建一个字符串 current，用于表示当前正在生成的括号组合。
2. 创建两个整数变量 left 和 right，分别表示已使用的左括号和右括号的数量。
3. 使用回溯法生成括号组合：
   1. 如果 left 小于 n，可以添加一个左括号，并递归处理下一个字符。
   2. 如果 right 小于 left，可以添加一个右括号，并递归处理下一个字符。
   3. 当 left 和 right 都等于 n 时，表示已生成一个合法的括号组合，将 current 添加到结果中。
4. 递归结束条件是 current 的长度等于 2n。
5. 返回结果数组，其中包含所有合法的括号组合。

参考代码：

#include <iostream>
#include <vector>
#include <string>

class ParenthesesGenerator {
public:
    std::vector<std::string> generateParenthesis(int n) {
        std::vector<std::string> result;  // 用于存储合法的括号组合
        std::string current;  // 当前括号组合
        backtrack(result, current, 0, 0, n);
        return result;
    }

private:
    void backtrack(std::vector<std::string>& result, std::string& current, int left, int right, int n) {
        if (current.length() == 2 * n) {
            result.push_back(current);
            return;
        }

        if (left < n) {
            current.push_back('(');  // 添加左括号
            backtrack(result, current, left + 1, right, n);  // 递归处理下一个字符
            current.pop_back();  // 撤销添加的左括号
        }

        if (right < left) {
            current.push_back(')');  // 添加右括号
            backtrack(result, current, left, right + 1, n);  // 递归处理下一个字符
            current.pop_back();  // 撤销添加的右括号
        }
    }
};

int main() {
    ParenthesesGenerator generator;
    int n = 3;
    std::vector<std::string> combinations = generator.generateParenthesis(n);

    std::cout << "括号组合：\n";
    for (const std::string& combination : combinations) {
        std::cout << combination << std::endl;
    }

    return 0;
}

7、矩阵最长递增路径

7.1、问题描述

给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。 你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。

这个路径必须满足以下条件：

1. 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
2. 你不能走重复的单元格。即每个格子最多只能走一次。

例如：当输入为[[1,2,3],[4,5,6],[7,8,9]]时，对应的输出为5，

其中的一条最长递增路径如下图所示：

示例1

输入：[[1,2,3],[4,5,6],[7,8,9]]

返回值：5

说明：1->2->3->6->9即可。当然这种递增路径不是唯一的。

示例2

输入：[[1,2],[4,3]]

返回值：4

说明： 1->2->3->4

7.2、思路及代码

思路：

1. 定义一个longestIncreasingPath函数，输入矩阵matrix，用于计算最长递增路径长度。
2. 首先检查输入矩阵是否为空，若为空则返回0。
3. 获取矩阵的行数和列数，初始化一个memo数组，用于存储每个单元格的最长路径长度，初始值都为0，以及一个变量maxLength用于记录最长路径长度。
4. 使用嵌套循环遍历矩阵的每个单元格。
5. 对于每个单元格，调用dfs函数计算以当前单元格为起点的最长递增路径长度，然后更新maxLength。
6. 返回maxLength作为结果。

参考代码：

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) {
            return 0; // 如果矩阵为空，直接返回0
        }

        int rows = matrix.size(); // 获取矩阵的行数
        int cols = matrix[0].size(); // 获取矩阵的列数

        // 创建一个二维数组memo，用于存储每个单元格的最长递增路径长度，初始值都为0
        std::vector<std::vector<int>> memo(rows, std::vector<int>(cols, 0));

        int maxLength = 0; // 用于记录最长递增路径的长度

        // 遍历矩阵的每个单元格
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                // 对于每个单元格，调用dfs函数计算最长递增路径
                int pathLength = dfs(matrix, i, j, memo);
                maxLength = std::max(maxLength, pathLength); // 更新最大长度
            }
        }

        return maxLength; // 返回最长递增路径的长度
    }

private:
    // 深度优先搜索函数，用于计算以(x, y)为起点的最长递增路径
    int dfs(const std::vector<std::vector<int>>& matrix, int x, int y, std::vector<std::vector<int>>& memo) {
        if (memo[x][y] != 0) {
            return memo[x][y]; // 如果已经计算过该点的最长路径，直接返回
        }

        static std::vector<int> dx = {0, 1, 0, -1};
        static std::vector<int> dy = {1, 0, -1, 0};

        int maxLength = 1; // 起始路径长度为1

        // 尝试从当前点向四个方向移动
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            // 检查新坐标(nx, ny)是否在矩阵内，且满足递增条件
            if (nx >= 0 && nx < matrix.size() && ny >= 0 && ny < matrix[0].size() && matrix[nx][ny] > matrix[x][y]) {
                // 计算新路径的长度（当前长度加1，并递归计算）
                int pathLength = 1 + dfs(matrix, nx, ny, memo);
                maxLength = std::max(maxLength, pathLength); // 更新最大长度
            }
        }

        memo[x][y] = maxLength; // 将计算结果存储在memo中
        return maxLength;
    }
};

int main() {
    Solution solution;
    std::vector<std::vector<int>> matrix = {
        {9, 9, 4},
        {6, 6, 8},
        {2, 1, 1}
    };
    int maxLength = solution.longestIncreasingPath(matrix);

    std::cout << "最长递增路径的长度为: " << maxLength << std::endl;

    return 0;
}