首页 > 代码库 > Leetcode:Permutations

Leetcode:Permutations

2024-11-01 23:47:39   207人阅读

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].

分析：此题既可以迭代法解也可以用递归的方法解。

这里先介绍递归的方法。递归的方法类似DFS，一个permutation是遍历过程中生成的一个大小等于所有number数的路径。那么利用递归生成这个路径呢？决定一个permutation的是permutation中元素的位置，假设现在我们要确定permutation第i个位置的元素，我们需要做的是把所以可以放在第i个位置的元素都试一下，然后递归的确定可以放在第i+1个位置的元素。这样当确定完最后一个位置的元素后，我们便得到了一个permutation。代码如下：

class Solution {public:    vector<vector<int> > permute(vector<int> &num) {        vector<vector<int> > result;        vector<int> path;                dfs(result, path, num);                return result;    }        void dfs(vector<vector<int> > &result, vector<int> &path, vector<int> &num){        if(path.size() == num.size()){            result.push_back(path);            return;        }        for(auto i:num){            if(find(path.begin(), path.end(), i) == path.end()){                path.push_back(i);                dfs(result, path, num);                path.pop_back();            }        }    }};

迭代的方法是利用next_permutation，先将num按ascending排序，然后从最小的permutation逐次求next_permutation，直到最大的permutation为止。代码如下：

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

 

Leetcode:Permutations


联系
我们