46. Permutations(全排列问题--回溯问题经典)
Given a collection of distinct numbers, return all possible permutations.
For example,
<code>[1,2,3]</code> have the following permutations:
题目大意:求一个序列的全排列。
代码如下:(采用典型的回溯来处理)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<code>class</code> <code>Solution {</code>
<code>public</code><code>:</code>
<code> </code><code>void</code> <code>permuteHelper(vector<vector<</code><code>int</code><code>> >& result,vector<</code><code>int</code><code>> &tmp,vector<</code><code>int</code><code>>& nums)</code>
<code> </code><code>{</code>
<code> </code><code>if</code><code>(nums.empty())</code>
<code> </code><code>{</code>
<code> </code><code>result.push_back(tmp);</code>
<code> </code><code>return</code><code>;</code>
<code> </code><code>}</code>
<code> </code>
<code> </code><code>for</code><code>(</code><code>int</code> <code>i = 0; i < nums.size(); i++)</code>
<code> </code><code>int</code> <code>val = nums[i];</code>
<code> </code><code>tmp.push_back(val);</code>
<code> </code><code>nums.erase(nums.begin()+i);</code>
<code> </code><code>permuteHelper(result,tmp,nums);</code>
<code> </code><code>nums.insert(nums.begin()+i,val);</code>
<code> </code><code>tmp.pop_back();</code>
<code> </code><code>}</code>
<code> </code><code>vector<vector<</code><code>int</code><code>>> permute(vector<</code><code>int</code><code>>& nums) {</code>
<code> </code><code>vector<vector<</code><code>int</code><code>>> result;</code>
<code> </code><code>vector<</code><code>int</code><code>> tmp;</code>
<code> </code><code>permuteHelper(result,tmp,nums);</code>
<code> </code><code>return</code> <code>result;</code>
<code>};</code>
2016-08-07 15:11:04
本文转自313119992 51CTO博客,原文链接:http://blog.51cto.com/qiaopeng688/1835352