首页 > 代码库 > [leetcode] Permutations
[leetcode] Permutations
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].
思路：
dfs搜索。visited[]数组表示对应的数字是否已经使用，visited[i]==true，表示num[i]已经使用。一直递归搜索，寻找没有使用过的数字，组成全排列。
这里给visited数组赋值的时候，开始写成了sizeof(int)，提交出现runtime error，但是在vs2010下可以得出正确结果；后来发现换成了sizeof(bool)就通过了。这个估计和编译器有关，可以研究一下。
题解：
class Solution {public: vector<vector<int> > res; vector<int> tmp; void dfs(vector<int> &num, bool visited[], int index) { if(index==num.size()) { res.push_back(tmp); return; } for(int i=0;i<num.size();i++) { if(visited[i]) continue; visited[i] = true; tmp.push_back(num[i]); dfs(num, visited, index+1); tmp.pop_back(); visited[i] = false; } } vector<vector<int> > permute(vector<int> &num) { int n = num.size(); bool *visited = new bool [n]; memset(visited, false, sizeof(bool)*n); dfs(num, visited, 0); return res; }};
后记：
提交出现runtime error时，就在网上找了一下大神们的解法，发现了一种交换排序的方法，似乎逻辑更严密一些，尤其是在全排列系列的题目特别有帮助。这里就不放代码了，给出链接。
[leetcode] Permutations
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。