字符串的排列（dfs）1

题目要求实现一个功能，输入一个字符串，然后输出这个字符串中所有可能的排列组合。这个问题属于经典的全排列问题，可以通过深度优先搜索（DFS）算法解决。接下来我们将深入探讨这个算法及其在给定代码中的应用。 我们需要理解DFS的概念。深度优先搜索是一种用于遍历或搜索树或图的算法。在这个问题中，我们将字符串视为字符的集合，通过DFS来生成所有可能的排列组合。DFS的特点是从根节点开始，沿着一条路径一直走下去，直到达到叶子节点或者遇到回溯条件，然后再回溯到上一层节点，选择其他未访问过的分支继续探索。 在给定的代码中，定义了一个名为`Solution`的类，其中包含一个`permutation`函数作为主入口，它接收一个字符串`s`作为输入，并返回一个包含所有排列的字符串向量`res`。代码还定义了一个`set<string>`类型的变量`ss`用于存储中间结果以去重，以及一个`vector<string>`类型的`res`用于最终返回结果。 `Solution`类中有两个关键函数：`dfs`（深度优先搜索）和`permutation`。 1. `dfs`函数： - 参数：`str`是原始输入字符串，`tmp`是正在构建的临时字符串，`used`是一个布尔向量，标记`str`中的字符是否已被使用。 - 当`tmp`的长度等于`str`时，说明一个排列完成，将其添加到`ss`中进行去重。 - 如果`tmp`的长度小于`str`，则遍历`str`的每个字符，如果该字符未被使用，则将其添加到`tmp`中，标记为已使用，然后递归调用`dfs`继续构造新的排列。 - 递归结束后，需要回溯，即还原`used`的状态，从`tmp`中移除最后一个字符，以便尝试其他的字符排列。 2. `permutation`函数： - 初始化`tmp`为空字符串，`used`全部初始化为`false`，表示所有字符未使用。 - 调用`dfs`函数开始搜索所有可能的排列。 - 从去重后的`ss`中取出所有排列，添加到`res`中。 - 返回`res`作为最终结果。 整个算法的核心在于`dfs`函数，它利用递归的方式构建所有可能的字符串排列。由于每次构造新字符串时，都会检查已使用的字符并进行回溯，所以不会产生重复的排列。在`permutation`函数中，我们先使用`dfs`得到所有排列，然后将结果存入`res`，最后返回`res`。 例如，对于输入字符串`s = "abc"`，`dfs`函数会生成以下过程： 1. 初始化：`tmp`为空，`used`为`[false, false, false]`。 2. 首次调用`dfs("abc", "", [false, false, false])`。 3. 排列1：`dfs("abc", "a", [true, false, false])` -> `dfs("abc", "ab", [true, true, false])` -> `dfs("abc", "abc", [true, true, true])`，将"abc"存入`ss`。 4. 回溯：`dfs("abc", "abc", [true, true, false])` -> `dfs("abc", "ab", [true, false, false])` -> `dfs("abc", "ac", [true, false, true])`，将"acb"存入`ss`。 5. 回溯：`dfs("abc", "ac", [true, false, false])` -> `dfs("abc", "a", [true, false, false])`，继续尝试下一个字符。 6. 排列2：`dfs("abc", "a", [true, false, false])` -> `dfs("abc", "ac", [true, true, false])` -> `dfs("abc", "bac", [true, true, true])`，将"bac"存入`ss`。 7. 回溯：`dfs("abc", "bac", [true, true, false])` -> `dfs("abc", "ac", [true, true, false])` -> `dfs("abc", "ca", [false, true, true])`，将"bca"存入`ss`。 8. ...以此类推，生成所有可能的排列。 `res`将包含所有无重复的排列，如`["abc", "acb", "bac", "bca", "cab", "cba"]`。