leetCode 46. Permutations 回溯問題 | Medium

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&lt;vector&lt;</code><code>int</code><code>&gt; &gt;&amp; result,vector&lt;</code><code>int</code><code>&gt; &amp;tmp,vector&lt;</code><code>int</code><code>&gt;&amp; 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 &lt; 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&lt;vector&lt;</code><code>int</code><code>&gt;&gt; permute(vector&lt;</code><code>int</code><code>&gt;&amp; nums) {</code>

<code>        </code><code>vector&lt;vector&lt;</code><code>int</code><code>&gt;&gt; result;</code>

<code>        </code><code>vector&lt;</code><code>int</code><code>&gt; 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