首页 > 代码库 > 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].
Hide Tags
Backtracking建立一棵树，比如说
1234
1234 2134 3214 4231 //就是swap(1,1) swap(1,2) swap(1,3) swap(1,4)
|
1234 1324 1432 //就是swap(2,2) swap(2,3) swap(2,4)
|
1234 1243 //就是swap(3,3) swap(3,4)
然后，就用DFS遍历，叶子节点就是我们想要的
class Solution {private: vector<vector<int> > ret;public: void perm(vector<int> num,int i){ if(i==num.size()){ ret.push_back(num); return; } for(int j=i;j<num.size();j++){ swap(num[i],num[j]); perm(num,i+1); swap(num[j],num[i]); //复原，进行下一个交换前需复原之前状态 } } vector<vector<int> > permute(vector<int> &num) { perm(num,0); return ret; }};
Permutations 全排列 回溯
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。