题目一. 全排列II

1. 题⽬链接：

https://leetcode.cn/problems/permutations-ii/description/

2. 题⽬描述：

3. 解法：

算法思路：
因为题⽬不要求返回的排列顺序，因此我们可以对初始状态排序，将所有相同的元素放在各⾃相邻的
位置，⽅便之后操作。因为重复元素的存在，我们在选择元素进⾏全排列时，可能会存在重复排列，
例如：[1, 2, 1]，所有的 下标排列 为：

123
132
213
231
312
321

按照以上下标进⾏排列的结果为：

121
112
211
211
112
121

可以看到，有效排列只有三种[1, 1, 2]，[1, 2, 1]，[2, 1, 1]，其中每个排列都出现两次。因此，我们需要对相同元素定义⼀种规则，使得其组成的排列不会形成重复的情况：

1. 我们可以将相同的元素按照排序后的下标顺序出现在排列中，通俗来讲，若元素 s 出现 x 次，则排序后的第 2 个元素 s ⼀定出现在第 1 个元素 s 后⾯，排序后的第 3 个元素 s ⼀定出现在第 2 个元素 s 后⾯，以此类推，此时的全排列⼀定不会出现重复结果。

2. 例如：a1=1，a2=1，a3=2，排列结果为 [1, 1, 2] 的情况只有⼀次，即 a1 在 a2 前⾯，因为 a2 不会出现在 a1 前⾯从⽽避免了重复排列。

3. 我们在每⼀个位置上考虑所有的可能情况并且不出现重复；

4. 注意：若当前元素的前⼀个相同元素未出现在当前状态中，则当前元素也不能直接放⼊当前状态 的数组，此做法可以保证相同元素的排列顺序与排序后的相同元素的顺序相同，即避免了重复排列 出现。

5. 通过深度优先搜索的⽅式，不断地枚举每个数在当前位置的可能性，并在递归结束时回溯到上⼀个状态，直到枚举完所有可能性，得到正确的结果。

递归函数设计：

public void dfs(int[] nums, int pos) 参数：pos（当前需要填⼊的位置）； 返回值：⽆；
函数作⽤：查找所有合理的排列并存储在答案列表中。

递归流程如下：

1. 定义⼀个⼆维数组 ans ⽤来存放所有可能的排列，⼀个⼀维数组 perm ⽤来存放每个状态的排列， ⼀个⼀维数组 visited 标记元素，然后从第⼀个位置开始进⾏递归；

2. 在每个递归的状态中，我们维护⼀个步数 idx，表⽰当前已经处理了⼏个数字；

3. 递归结束条件：当 idx 等于 nums 数组的⻓度时，说明我们已经处理完了所有数字，将当前数组存 ⼊结果中；

4. 在每个递归状态中，枚举所有下标 i，若这个下标未被标记，并且在它之前的相同元素被标记过， 则使⽤ nums 数组中当前下标的元素：

a. 将 visited[i] 标记为 1；

b. 将 nums[i] 添加⾄ perm 数组末尾；

c. 对第 step+1 个位置进⾏递归；

d. 将 visited[i] 重新赋值为 0，并删除 perm 末尾元素表⽰回溯；

5. 最后，返回 ans。 C++ 算法代码：

4.代码

class Solution 
{List<Integer> path;List<List<Integer>> ret;boolean[] check;public List<List<Integer>> permuteUnique(int[] nums) {path = new ArrayList<>();ret = new ArrayList<>();check = new boolean[nums.length];Arrays.sort(nums);dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos){if(pos == nums.length){ret.add(new ArrayList<>(path));return;}for(int i = 0; i < nums.length; i++){// 剪枝 if(check[i] == false && (i == 0 || nums[i] != nums[i - 1] || 
check[i - 1] != false)){path.add(nums[i]);check[i] = true;dfs(nums, pos + 1);// 回溯 -> 恢复现场 path.remove(path.size() - 1);check[i] = false;}}}
}

题目二. 电话号码的字⺟组合

1. 题⽬链接：

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

2. 题⽬描述：

3. 解法：

算法思路：
每个位置可选择的字符与其他位置并不冲突，因此不需要标记已经出现的字符，只需要将每个数字对
应的字符依次填⼊字符串中进⾏递归，在回溯是撤销填⼊操作即可。
• 在递归之前我们需要定义⼀个hash表，记录 2~9 各⾃对应的字符。

递归函数流程如下：

1. 递归结束条件：当 index 等于 digits 的⻓度时，将 ans 加⼊到 res 中并返回；

2. 取出当前处理的数字 digit，根据 phoneMap 取出对应的字⺟列表 letters；

3. 遍历字⺟列表 letters，将当前字⺟加⼊到组合字符串 ans 的末尾，然后递归处理下⼀个数字（传 ⼊ index + 1，表⽰处理下⼀个数字）；

4. 递归处理结束后，将加⼊的字⺟从 ans 的末尾删除，表⽰回溯。

5. 最终返回 res 即可。

4.代码

class Solution 
{String[] hash = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};List<String> ret;StringBuffer path;public List<String> letterCombinations(String digits) {ret = new ArrayList<>();path = new StringBuffer();if(digits.length() == 0) return ret;dfs(digits, 0);return ret;}public void dfs(String digits, int pos){if(pos == digits.length()){ret.add(path.toString());return;}String cur = hash[digits.charAt(pos) - '0'];for(int i = 0; i < cur.length(); i++){path.append(cur.charAt(i));dfs(digits, pos + 1);path.deleteCharAt(path.length() - 1); // 恢复现场 }}
}

题目三. 括号⽣成（medium）

1. 题⽬链接：

https://leetcode.cn/problems/generate-parentheses/description/

2. 题⽬描述：

3. 解法：

算法思路：
从左往右进⾏递归，在每个位置判断放置左右括号的可能性，若此时放置左括号合理，则放置左括号
继续进⾏递归，右括号同理。
⼀种判断括号是否合法的⽅法：从左往右遍历，左括号的数量始终⼤于等于右括号的数量，并且左括
号的总数量与右括号的总数量相等。因此我们在递归时需要进⾏以下判断：

1. 放⼊左括号时需判断此时左括号数量是否⼩于字符串总⻓度的⼀半（若左括号的数量⼤于等于字符 串⻓度的⼀半时继续放置左括号，则左括号的总数量⼀定⼤于右括号的总数量）；

2. 放⼊右括号时需判断此时右括号数量是否⼩于左括号数量

递归流程如下：

1. 递归结束条件：当前状态字符串⻓度与 2*n 相等，记录当前状态并返回；

2. 若此时左括号数量⼩于字符串总⻓度的⼀半，则在当前状态的字符串末尾添加左括号并继续递归， 递归结束撤销添加操作；

3. 若此时右括号数量⼩于左括号数量（右括号数量可以由当前状态的字符串⻓度减去左括号数量求 得），则在当前状态的字符串末尾添加右括号并递归，递归结束撤销添加操作

代码

class Solution 
{int left, right, n;StringBuffer path;List<String> ret;public List<String> generateParenthesis(int _n) {n = _n;path = new StringBuffer();ret = new ArrayList<>();dfs();return ret;}public void dfs(){if(right == n){ret.add(path.toString());return;}if(left < n) // 添加左括号 {path.append('('); left++;dfs();path.deleteCharAt(path.length() - 1); left--; // 恢复现场 }if(right < left) // 添加哎右括号 {path.append(')'); right++;dfs();path.deleteCharAt(path.length() - 1); right--; // 恢复现场 }}
}