传送门

经 典 老 番

最近算法课讲到递归，顺手写一点经典的回溯题来巩固基础。

回溯是一种通过枚举出所有可能情况来得到解答的算法，很直白也很经典。当确定当前情况不是解或不是最后一个解时，算法会逐步退回到之前的步骤，通过更改部分组成来枚举下一种情况。

放在这道题里，要得出n个数的全排列，不难得出它的递归思路，设cur为当前操作到的元素下标：

  1. cur==n，排列完了所有数，当前排列作为一个答案存储。
  2. 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;
    }
};