1 题目
题目：全排列（Permutations）
描述：给定一个数字列表，返回其所有可能的排列。假设没有重复的数字。
lintcode题号——15，难度——medium
样例1：
输入：列表 = [1]
输出：
[
[1]
]
样例2：
输入：列表 = [1,2,3]
输出：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
2 解决方案
2.1 思路
??寻找所有的排列，考虑使用深度优先搜索（Depth First Search），递归时需要去重，去重不能直接跳过当前元素向后取，因为所有元素在结果里都必须需要出现一次，根据递归的分析图，需要在竖直分支上去重（区别于同一层级去重），考虑使用set数据结构的特性（重复元素只能插入一次）来进行去重。
DFS常用于需要遍历出所有解的场景中，例如求所有子集、得到所有组合、全排列等经典问题。
2.2 图解
nums = [1,2,3]的情况下，深度优先搜索的图如下：
去重——去掉同一竖直分支上的包含重复元素的解（上图虚线解），结果如下：
2.3 时间复杂度
??深度优先搜索的时间复杂度是逻辑图上的节点数（即所有元素的组合数，n个元素，每个元素都有取或不取两种可能，所以是2的n次方）与处理每个节点的耗时（for循环n次）的乘积，该题的算法的时间复杂度为O(2^n * n)。
深度优先搜索的时间复杂度计算没有通用的方式，只能根据具体题目计算，可以理解成看作答案个数与构造每个答案花费的时间的乘积。
2.4 空间复杂度
??使用了vector和set数据结构保存节点，算法的空间复杂度为O(n)。
3 源码
细节：
- 使用set进行
同一分支去重（纵向），set要放在参数里向下传递，沿分支路径向下去重（需要回溯），注意区别同一层级去重（不需要回溯）。 - 空集返回的是[[]]，而不是[]。
也可以使用
vector<bool>对相应的元素进行标记来完成去重，更为通用。
C++版本：
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int>> permute(vector<int> &nums) {
// write your code here
vector<vector<int>> results;
if (nums.empty())
{
results.push_back(vector<int>());
return results;
}
vector<int> path; // 当前的排列
set<int> usedElement; // 已使用的元素
// 递归的定义
dfs(nums, usedElement, path, results);
return results;
}
void dfs(vector<int> & nums, set<int> & usedElement, vector<int> & path, vector<vector<int>> & results)
{
// 递归的出口
if (path.size() == nums.size())
{
results.push_back(path);
return;
}
// 递归的拆解
for (int i = 0; i < nums.size(); i++)
{
if (usedElement.find(nums.at(i)) != usedElement.end())
{
continue;
}
usedElement.insert(nums.at(i));
path.push_back(nums.at(i));
dfs(nums, usedElement, path, results);
path.pop_back();
usedElement.erase(nums.at(i));
}
}
4 另解
4.1 交换法
- 依次以一个元素为头，找到以该元素为头进行变换而成的所有排列结果。
- 变换的方式为依次交换之后的每个元素与该头元素，从而形成不同的排列结果。
算法实际递归过程是自顶向下计算，但可以自底向上来理解，例如abcde，先排e，加入新的头元素d，形成d[e]，d[e]按照规则
2变换出ed，形成子集[de]和[ed]，再加入新的头元素c，形成cde和ced，c[de]按照规则2变换出dce和edc，而c[ed]变换出ecd和dec，形成子集dce、edc、ecd、dec，再以此类推加入新的头元素b……
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int>> permute(vector<int> &nums) {
// write your code here
vector<vector<int>> results;
if (nums.empty())
{
return results;
}
// 递归定义，全排列startIndex向后的序列，存入results中
subPermute(nums, 0, results);
return results;
}
void subPermute(vector<int> & nums, int startIndex, vector<vector<int>> & results)
{
// 递归出口
if (startIndex == nums.size() - 1)
{
results.push_back(nums);
return;
}
// 递归的拆解
for (int i = offset; i < nums.size(); i++)
{
// 以startIndex位置的元素为头，每次与之后的元素交换，并全排列startIndex+1的序列，每次到最后一个元素即可形成一个结果
swap(nums.at(startIndex), nums.at(i));
subPermute(nums, startIndex + 1, results);
// 回溯
swap(nums.at(startIndex), nums.at(i));
}
}
4.2 插空法
- 将元素按照插空法逐个加入结果，直到所有元素都加入排列。
- 新加入的元素不必关心已经加入的元素的位置，只关心有哪些空位可以插入。
算法通过不断向已有序列中加入元素来完成排列，例如abcde，先排a，此时加入新的元素b有两个空位（a的左边和右边），可以形成ab和ba，两种排列，再加入新的元素c有三个空位（n个元素有n+1个空位），配合ab形成cab、acb、abc，配置ba形成cba、bca、bac，六种排列，再以此类推加入新的元素d……
/**
* @param nums: A list of integers.
* @return: A list of permutations.
*/
vector<vector<int>> permute(vector<int> &nums) {
// write your code here
vector<vector<int>> results;
if (nums.empty())
{
results.push_back(vector<int>());
return results;
}
vector<int> remainSet = nums;
subPermute(vector<int>(), remainSet, results); // 开始时基础序列为空
return results;
}
// 递归的定义
void subPermute(vector<int> baseSet, vector<int> remainSet, vector<vector<int>> &results)
{
// 递归的出口
if (remainSet.empty())
{
results.push_back(baseSet);
return;
}
for (int i = 0; i <= baseSet.size(); i++)
{
// 向基础序列加入元素
baseSet.insert(baseSet.begin() + i, remainSet.front());
int tmp = remainSet.front();
remainSet.erase(remainSet.begin());
// 递归的拆解
subPermute(baseSet, remainSet, results);
// 回溯
baseSet.erase(baseSet.begin() + i);
remainSet.insert(remainSet.begin(), tmp);
}
}
