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