題目:permute
要求:
給定一個數字列表，返回其所有可能的排列。 注意事項你可以假設沒有重復數字。樣例:
給出一個列表[1,2,3]，其全排列為：[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]算法要求:
使用遞歸和非遞歸分別解決。解題思路:
只寫出來遞歸的方法，思路就是m位與其他位依次交換，直到m等于總個數的時候（這個時候就是無法交換了）存入到vector容器里。m是從0~總個數的，而且m只跟m后面的進行交換，這樣就不會出現重復交換了。注意當函數到了遞歸出口的時候，簡單來說就是我存進去一個，就將它還原成上一個。非遞歸的方法想出來就會再來補充。算法如下:
vector<vector<int> > mainVec; void permute(vector<int> &nums, int m) { int temp; if (m == nums.size()) { mainVec.push_back(nums); } else { for (int i = m; i < nums.size(); i++) { temp = nums[m]; nums[m] = nums[i]; nums[i] = temp; permute(nums, m+1); temp = nums[m]; nums[m] = nums[i]; nums[i] = temp; } } } vector<vector<int> > permute(vector<int> nums) { mainVec.clear(); permute(nums, 0); return mainVec; }
