目录
全排列Ⅱ（medium）
题目解析
讲解算法原理
编写代码
电话号码的字⺟组合（medium）
题目解析
讲解算法原理
编写代码
全排列Ⅱ（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个可包含重复数字的序列nums，按任意顺序返回所有不重复的全排列。
• ⽰例1：
输⼊：nums=[1,1,2]输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
• ⽰例2：
输⼊：nums=[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
• 提⽰：
1<=nums.length<=8
-10<=nums[i]<=10
讲解算法原理
解法：算法思路：
因为题⽬不要求返回的排列顺序，因此我们可以对初始状态排序，将所有相同的元素放在各⾃相邻的
位置，⽅便之后操作。因为重复元素的存在，我们在选择元素进⾏全排列时，可能会存在重复排列，例如：[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. 通过深度优先搜索的⽅式，不断地枚举每个数在当前位置的可能性，并在递归结束时回溯到上⼀个状态，直到枚举完所有可能性，得到正确的结果。
递归函数设计：voidbacktrack(vector<int>&nums,intidx)参数：idx（当前需要填⼊的位置）；
返回值：⽆；函数作⽤：查找所有合理的排列并存储在答案列表中。
递归流程如下：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++算法代码：
class Solution
{
vector<int> path;
vector<vector<int>> ret;
bool check[9];
public:
vector<vector<int>> permuteUnique(vector<int>& nums)
{
sort(nums.begin(), nums.end());
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
if(pos == nums.size())
{
ret.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++)
{
// 剪枝
if(check[i] == false && (i == 0 || nums[i] != nums[i - 1] ||
check[i - 1] != false))
{
path.push_back(nums[i]);
check[i] = true;
dfs(nums, pos + 1);
path.pop_back(); // 恢复现场
check[i] = false;
}
}
}
};java算法代码：
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;
}
}
}
}电话号码的字⺟组合（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个仅包含数字2-9的字符串，返回所有它能表⽰的字⺟组合。答案可以按任意顺序返回。给出数字到字⺟的映射如下（与电话按键相同）。注意1不对应任何字⺟。
• ⽰例1：
输⼊：digits="23"输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
• ⽰例2：
输⼊：digits=""输出：[]
• ⽰例3：
输⼊：digits="2"输出：["a","b","c"]
• 提⽰：
0<=digits.length<=4
digits[i]是范围['2','9']的⼀个数字。
讲解算法原理
解法：
算法思路：
每个位置可选择的字符与其他位置并不冲突，因此不需要标记已经出现的字符，只需要将每个数字对应的字符依次填⼊字符串中进⾏递归，在回溯是撤销填⼊操作即可。
• 在递归之前我们需要定义⼀个字典phoneMap，记录2~9各⾃对应的字符。
递归函数设计：voidbacktrack(unordered_map<char,string>&phoneMap,string&digits,intindex)
参数：index（已经处理的元素个数），ans（字符串当前状态），res（所有成⽴的字符串）；返回值：⽆
函数作⽤：查找所有合理的字⺟组合并存储在答案列表中。
递归函数流程如下：
1. 递归结束条件：当index等于digits的⻓度时，将ans加⼊到res中并返回；
2. 取出当前处理的数字digit，根据phoneMap取出对应的字⺟列表letters；
3. 遍历字⺟列表letters，将当前字⺟加⼊到组合字符串ans的末尾，然后递归处理下⼀个数字（传⼊index+1，表⽰处理下⼀个数字）；
4. 递归处理结束后，将加⼊的字⺟从ans的末尾删除，表⽰回溯。
5. 最终返回res即可。
编写代码
c++算法代码：
class Solution
{
string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs",
"tuv", "wxyz"};
string path;
vector<string> ret;
public:
vector<string> letterCombinations(string digits)
{
if(digits.size() == 0) return ret;
dfs(digits, 0);
return ret;
}
void dfs(string& digits, int pos)
{
if(pos == digits.size())
{
ret.push_back(path);
return;
}
for(auto ch : hash[digits[pos] - '0'])
{
path.push_back(ch);
dfs(digits, pos + 1);
path.pop_back(); // 恢复现场
}
}
};java算法代码：
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); // 恢复现场 }
}
}
