经 典 老 番
最近算法课讲到递归，顺手写一点经典的回溯题来巩固基础。
回溯是一种通过枚举出所有可能情况来得到解答的算法，很直白也很经典。当确定当前情况不是解或不是最后一个解时，算法会逐步退回到之前的步骤，通过更改部分组成来枚举下一种情况。
放在这道题里，要得出n个数的全排列，不难得出它的递归思路，设cur为当前操作到的元素下标：
- cur==n，排列完了所有数，当前排列作为一个答案存储。
- cur<n，考虑第cur个位置填哪个数。这个数不能被用过，所以需要借助一个vis数组来判断。如果vis[nums[cur]]==0，那么可以填入当前数，填入后继续递归dfs(cur+1,n,nums)执行下一次操作。
回溯时会撤销这个被填入的数与标记，并尝试下一个数。
上述思路是回溯的基本想法，但就这题而言可以避免vis数组的使用，以节约少部分空间。
上述算法需要借助标记数组，是为了去判断当前数可否填入。
考虑一种新的做法，以cur为界，左边是已经执行过操作的数，右边是等待操作的数。为了维护这种结构，可以使用swap直接在nums数组上操作。
class Solution {
private:
vector< vector<int> > ans;
void dfs(int cur, int len, vector<int>& nums) {
if(cur == len) {
ans.push_back(nums);
return;
}
for(int i = cur; i < len; i++) {
swap(nums[i], nums[cur]);
dfs(cur+1, len, nums);
swap(nums[i], nums[cur]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
dfs(0, nums.size(), nums);
return ans;
}
};