Leetcode: Permutations

本文主要是介绍Leetcode: Permutations，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：
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]. 

思路分析：
思路一：
最容易想到的就是递归了！每次在num中拿出1个数字放在第一个，然后剩下的数字做一个全排列。
C++参考代码：

class Solution
{
public:vector<vector<int> > permute(vector<int> &num){int size = int(num.size());vector<vector<int>> result;//num全排列的结果if (1 == size){result.push_back(num);return result;}vector<int> currentElement;//临时保存当前的numvector<vector<int>> remainingResult;//num除去一个元素以后剩下元素的全排列结果vector<int> currentResult;//保存当前num的每个全排列for (int i = 0; i < size; ++i){currentElement = num;currentElement.erase(currentElement.begin() + i);//去掉第i个元素（从0开始）remainingResult = permute(currentElement);//后续元素的全排列int remainingResultSize = int(remainingResult.size());for (int j = 0; j < remainingResultSize; ++j){currentResult = remainingResult[j];currentResult.insert(currentResult.begin(), num[i]);//在开始位置插入num[i]result.push_back(currentResult);}}return result;}
};

思路二：
同样使用递归：每次循环交换第一个元素和后面元素的位置，然后第一个元素和后面元素的全排列依次加入结果数组中。比如：

对于数组[1,2,3]
1. 交换1和1的位置（其实第一次不用交换），生成[2, 3]的全排列[2, 3]和[3, 2]，然后把1加上去生成[1, 2, 3]和[1, 3, 2]。交换完以后换回来。
2. 交换1和2的位置，生成[1, 3]的全排列[1, 3]和[3, 1]，然后把2加上去生成[2, 1, 3]和[2, 3, 1]。交换完以后换回来。
3. 交换1和3的位置，生成[2, 1]的全排列[2, 1]和[1, 2]，然后把3加上去生成[3, 2, 1]和[3, 1, 2]。交换完以后换回来

其实思路一和思路一有相似之处：都是选出一个元素，剩余元素做全排列。不同的是一：循环遍历给定数组进行计算；二通过交换第一个元素和后面元素的位置，结果为第一个元素+后面元素的全排列。
C++参考代码：

class Solution {
private:vector<vector<int>> result;int size;void permuate(vector<int> &num, int index){if (index == size){result.push_back(num);return;}for (int i = index; i < size; ++i){swap(num[index], num[i]);//交换i和index元素permuate(num, index + 1);//计算除去index元素，后面元素的全排列swap(num[index], num[i]);//再换回来}}
public:vector<vector<int> > permute(vector<int> &num){size = int(num.size());permuate(num, 0);return result;}
};

思路三：
使用STL提供的next_permutation函数，next_permutation函数能够以字典序列的方式输出排列的结果，详见：next_permutation。不过直接调用库函数貌似没有体现自己的思考与自己的算法！
C++参考代码：

class Solution
{
public:vector<vector<int> > permute(vector<int> &num){  vector<vector<int> > result;sort(num.begin(), num.end());//给num升序排序result.push_back(num);while (next_permutation(num.begin(), num.end())){result.push_back(num);}return result; }  
};

这篇关于Leetcode: Permutations的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---