您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
46. Permutations(全排列问题--回溯问题经典)
Given a collection of distinct 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], [3,2,1] ]
题目大意:求一个序列的全排列。
思路:做排列组合时,模拟该过程得到思路。首先选择集合中的某一个元素作为第一位,接着在剩下的元素中选择一个元素作为第二位,一直到为空。
上述过程显然是个递归的过程,声明帮助函数:Helper(vector<vector<int> >& result, vector<int>& tmp, vector<int>& nums)。tmp用来存储已经选定的元素,nums用来存储剩下的元素,result存储所得的情况。显然当nums为空的时候递归应该返回。
注意:关键在于对nums和tmp的处理,一旦tmp中增加了一个元素,nums就要删除该元素;每次有一个帮助函数返回时都会进行一次回溯,即nums要插入元素,tmp要删除元素。
代码如下:(采用典型的回溯来处理)
class Solution { public: void permuteHelper(vector<vector<int> >& result,vector<int> &tmp,vector<int>& nums) { if(nums.empty()) { result.push_back(tmp); return; } for(int i = 0; i < nums.size(); i++) { int val = nums[i]; tmp.push_back(val); nums.erase(nums.begin()+i); permuteHelper(result,tmp,nums); nums.insert(nums.begin()+i,val); tmp.pop_back(); } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> result; vector<int> tmp; permuteHelper(result,tmp,nums); return result; } };
2016-08-07 15:11:04
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。