排列问题DFS入门

1、题目描述（全排列）

输入一个正整数n，输出1~n的全排列。

输入格式

一个正整数n。

输出格式

所有1~n的全排列，每个排列占一行。

样例输入

3

样例输出

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法思路

题目要求输出n的全排列，因此我们可以使用深度优先搜索算法来解决问题。首先我们可以假设我们已经构建了一个长度为n的排列，并且我们想要把它输出。根据递归算法的设计思想，我们只需要先递归到当前排列中的下一个位置，然后在每个位置上枚举所有可以占用的数字，将它们依次填入当前位置中并递归到下一个位置即可。

当然，我们需要注意以下细节：

• 当我们递归到了最后一个位置时，我们只需要输出当前排列即可。

• 每个数字只能使用一次，因此在枚举可用数字时需要跳过已经被占用的数字。

• 同样地，我们需要一个辅助数组used来记录每个数字是否被占用。

代码：

#include <iostream>
#include <algorithm>
using namespace std;void dfs(int n, int depth, int* arr, bool* used) {if (depth == n) {//递归到了最后一个位置，输出当前排列即可for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;return;//退出递归}for (int i = 1; i <= n; i++) {if (!used[i]) {//说明i号数字还没有用过，可以放入这一层递归arr[depth] = i;//把i号数字放进去used[i] = true;//此时i号数字已经被使用dfs(n, depth + 1, arr, used);//自己调用自己，表示此时进入了第deoth+1层used[i] = false;//恢复初始状态（回溯的时候要用到）//相当于这一次的排列，数字已经全部放完了，需要按照顺序将数字拿回来，重新放}}
}int main() {int n;cin >> n;int arr[n];bool used[n + 1] = {false};dfs(n, 0, arr, used);return 0;
}

当然了，这里是为了说明DFS的用法，如果只是单纯求解全排列问题，我们可以直接使用next_permutation函数，代码如下：

#include <iostream>
#include <algorithm>
using namespace std;int main() {int n;cin >> n;int arr[n];for (int i = 0; i < n; i++) {arr[i] = i + 1;}do {for (int i = 0; i < n; i++) {cout << arr[i] << " ";}cout << endl;} while (next_permutation(arr, arr + n));return 0;
}

2、题目描述

给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合 。以任意顺序返回输出。

示例 1：
输入：s = “a1b2”
输出：[“a1b2”, “a1B2”, “A1b2”, “A1B2”]
示例 2:
输入: s = “3z4”
输出: [“3z4”,“3Z4”]
提示:
1 <= s.length <= 12
s 由小写英文字母、大写英文字母和数字组成

解题思路：

题目要求找到字符串的所有可能结果，使用深度优先搜索（DFS）可以很好地解决问题。DFS过程可以利用回溯法，因为在DFS过程中，我们需要对字符串进行修改，换而言之，就是我们需要在搜索结束之后将字符串还原，使其能够继续遍历其他可能性。

代码

#include <iostream>
#include <vector>
#include <string>using namespace std;void dfs(string s, int index, vector<string>& res) {if (index == s.size()) {res.push_back(s);return;}dfs(s, index + 1, res);if (isalpha(s[index])) {s[index] ^= (1 << 5);dfs(s, index + 1, res);}
}vector<string> letterCasePermutation(string s) {vector<string> res;dfs(s, 0, res);return res;
}int main() {string s = "a1b2";vector<string> res = letterCasePermutation(s);for (auto str : res) {cout << str << endl;}return 0;
}