Given a collection of numbers, return all possible permutations.

For example,
[1,2,3]?have the following permutations:
[1,2,3],?[1,3,2],?[2,1,3],?[2,3,1],?[3,1,2], and?[3,2,1].

思路：遍歷數(shù)組，對(duì)于該字母，它可選擇與它之后的字母交換或者是不交換=>帶回溯的遞歸

class Solution { public:vector<vector<int> > permute(vector<int> &num) {result.clear(); dfs(num,0);return result;}void dfs(vector<int> num, int depth){if(depth == num.size()-1){result.push_back(num);return;}dfs(num,depth+1);int temp = num[depth];for(int i = depth+1;i< num.size(); i++){num[depth] = num[i];num[i] = temp;dfs(num,depth+1);num[i] = num[depth];num[depth] = temp;}}private:vector<vector<int> > result; };

?思路II：

當(dāng)字符串長(zhǎng)度為2時(shí) a1a2 a2a1
當(dāng)字符串長(zhǎng)度為3時(shí) a3a1a2 a1a3a2 a1a2a3 a3a2a1 a2a3a1 a2a1a3
比較可以得到 其實(shí)就是把a(bǔ)3(多出來(lái)的元素)插在長(zhǎng)度為2時(shí)的兩個(gè)字符串的任意位置

時(shí)間復(fù)雜度：三個(gè)for循環(huán) O(n3)

class Solution { public:vector<vector<int>> permute(vector<int>& nums) {int size = nums.size();int resultSize;int resultIndex; vector<vector<int>> result; vector<int> resultItem(1,nums[0]);result.push_back(resultItem);for(int i = 1; i <size; i++){ //nums[i] is the num to insertresultSize = result.size(); //resultSize in the preceeding insert iteratefor(int j = 0; j < resultSize; j++){ //iterate the array to do insertion result[j].push_back(nums[i]);resultIndex = j;for(int k = i-1; k >=0; k--){ //like insertion sort, adjust forward result.push_back(result[resultIndex]);result[result.size()-1][k+1] = result[resultIndex][k];result[result.size()-1][k] = result[resultIndex][k+1];resultIndex = result.size()-1;}}}return result;} };

?

轉(zhuǎn)載于:https://www.cnblogs.com/qionglouyuyu/p/4855304.html

總結(jié)

以上是生活随笔為你收集整理的46. Permutations (Back-Track,Sort)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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