经 典 老 番
最近算法课讲到递归,顺手写一点经典的回溯题来巩固基础。
回溯是一种通过枚举出所有可能情况来得到解答的算法,很直白也很经典。当确定当前情况不是解或不是最后一个解时,算法会逐步退回到之前的步骤,通过更改部分组成来枚举下一种情况。
放在这道题里,要得出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; } };
评论
还没有任何评论,你来说两句吧!