题. 数字排列
输入一组数字（可能包含重复数字），输出其所有的排列方式。
数据范围
输入数组长度 [0,6]。
样例
输入：[1,2,3]
输出：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]【题解】--- 回溯法
__回溯法__（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
在回溯法中，每次扩大当前部分解时，都面临一个可选的状态集合，新的部分解就通过在该集合中选择构造而成。这样的状态集合，其结构是一棵多叉树，每个树结点代表一个可能的部分解，它的儿子是在它的基础上生成的其他部分解。树根为初始状态，这样的状态集合称为状态空间树。
回溯法对任一解的生成，一般都采用逐步扩大解的方式。每前进一步，都试图在当前部分解的基础上扩大该部分解。它在问题的状态空间树中，从开始结点（根结点）出发，以深度优先搜索整个状态空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点成为新的活结点，并成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的活结点处，并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在状态空间中搜索，直到找到所要求的解或解空间中已无活结点时为止。
回溯法与穷举法有某些联系，它们都是基于试探的。 穷举法 要将一个解的各个部分全部生成后，才检查是否满足条件，若不满足，则直接放弃该完整解，然后再尝试另一个可能的完整解，它并没有沿着一个可能的完整解的各个部分逐步回退生成解的过程。
而对于 回溯法 ，一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件时，就放弃该步所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来。
本题由于有重复元素的存在，注意枚举的顺序：
- 先将所有数从小到大排序，这样相同的数会排在一起；
- 从左到右依次枚举每个数，每次将它放在一个空位上；
- 对于相同数，我们人为定序，就可以避免重复计算：我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 startstart，我们在枚举当前数时，只枚举 start+1,start+2,…,nstart+1,start+2,…,n 这些位置。
- 不要忘记递归前和回溯时，对状态进行更新。
复杂度分析：
搜索树最后一层共有n！个结点，加上最后一层记录结点的计算量O（n），故总时间复杂度为O(n x n!)。C++代码实现：
class Solution {
public:
vector<bool> st;
vector<int> path;
vector<vector<int>> ans;
vector<vector<int>> permutation(vector<int>& nums) {
sort(nums.begin(), nums.end());
st = vector<bool>(nums.size(), false);
path = vector<int>(nums.size());
dfs(nums, 0, 0);
return ans;
}
void dfs(vector<int>& nums, int u, int start)
{
if (u == nums.size())
{
ans.push_back(path);
return;
}
for (int i = start; i < nums.size(); i ++ )
if (!st[i])
{
st[i] = true;
path[i] = nums[u];
if (u + 1 < nums.size() && nums[u + 1] != nums[u])
dfs(nums, u + 1, 0);
else
dfs(nums, u + 1, i + 1);
st[i] = false;
}
}
};
