給定一個 沒有重復 數(shù)字的序列，返回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出:
[
? [1,2,3],
? [1,3,2],
? [2,1,3],
? [2,3,1],
? [3,1,2],
? [3,2,1]
]

?思路：遞歸的思路來實現(xiàn)，即固定第一位，對剩下的數(shù)字進行同樣的算法，直到把一個數(shù)組全部遍歷完。 用vector<vector<int>>& ans來保存全排列的數(shù)組， 用begin來表示需要全排列的起始位置，end來表示需要全排列的終止位置

class Solution { public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> result;int n = nums.size();core(result,nums,0,n-1);return result;}void core(vector<vector<int>>& result, vector<int>& nums, int start, int end){if(start==end){result.push_back(nums);return;}for(int i=start;i<=end;++i){swap(nums, i, start);core(result, nums, start+1, end);swap(nums, i, start);}}void swap(vector<int>& nums, int a, int b){int temp = nums[a];nums[a] = nums[b];nums[b] = temp;} };

優(yōu)化：nums按值傳遞，省去一次swap?

class Solution { public:void permute(vector<int>nums, vector<vector<int>>& ans, int begin, int end){if(begin > end){ans.push_back(nums);return;}else{for(int i = begin; i <= end; i++){swap(nums[begin], nums[i]);permute(nums, ans, begin+1, end); }}}vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;int len = nums.size()-1;permute(nums, ans, 0, len);return ans;} };

?

?

總結(jié)

以上是生活随笔為你收集整理的全排列—leetcode46的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。