Leet Code:Permutations

[Question]

link

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].

[Thought]

给定一个序列abcd， 可能的排列情况如图所示：

enter image description here

进行排列时先把序列划分成两部分，第一个字符和剩余的n-1个字符，然后对剩余的n-1个字符进行全排列。

为了得到序列的全排列，第一个字符要分别为序列中的每一个字符，所以可以使用一个循环交换首字符，然后对后面n-1那一部分进行递归调用。这里实际上是一个深度优先搜索(DFS),搜索到叶节点之后往回回溯，数组记录了从根节点到叶节点的路径，得到的是依次递增的全排列（把图从左向右看，是不是一棵树？）。

[Code]

Haiyang Xu 08 May 2014