Permutations
Permutations (leetcodelintcode)
Description
Given a list of numbers, return all possible permutations.
Notice
You can assume that there is no duplicate numbers in the list.
Example
For nums = [1,2,3], the permutations are:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Challenge
Do it without recursion.
解题思路
一、DFS
Permutation要求遍历得到所有长度为n的排列，与Subsets的实现相比较，有两点不一样的地方：一是只有在长度为n时才会记录；二是不再要求升序，所有排序都必须遍历到。
算法复杂度
- 时间复杂度：一般而言，搜索问题的复杂度可以这么计算
O(解的个数 * 产生解的复杂度)。在本题中解的个数为n!，产生一个解的复杂度最坏可以认为是n，故算法渐进性能的上界可以认为是O(n*n!)。这里的时间复杂度并未考虑查找list中是否包含重复元素的contain操作。 - 空间复杂度：使用临时空间
list保存中间结果，list最大长度为数组长度，故空间复杂度近似为O(n)。
易错点：
- 在往
result中添加结果时要新建一个list的 拷贝（深拷贝），这是因为 Java 中所有对象都是引用，如果添加的是list，在主程序中修改list时，result中的list对象也会被修改。
Java 实现
public
class
Solution
{
public
List
<
List
<
Integer
>
>
permute(
int
[] nums) {
List
<
List
<
Integer
>
>
result =
new
ArrayList
<
List
<
Integer
>
>
();
if
(nums ==
null
|| nums.length ==
0
) {
result.add(
new
ArrayList
<
Integer
>
());
// when nums = [], return [[]]
return
result;
}
List
<
Integer
>
list =
new
ArrayList
<
Integer
>
();
// 把以 list 开头的所有排列全部放到 result 中
// 把以空{}为开头的所有排列全部放到 result 中
// 把以{1},{2},{3}为开头的所有排列全部放到 result 中...
dfs(result, list, nums);
return
result;
}
private
void
dfs
(List
<
List
<
Integer
>
>
result,
List
<
Integer
>
list,
int
[] nums)
{
if
(list.size() == nums.length) {
result.add(
new
ArrayList
<
Integer
>
(list));
return
;
}
for
(
int
i =
0
; i
<
nums.length; i++) {
if
(list.contains(nums[i])) {
continue
;
}
list.add(nums[i]);
dfs(result, list, nums);
list.remove(list.size() -
1
);
}
}
}
二、插入法（非递归）
以题目中的输入数组[1, 2, 3]举例说明：
- 当只有
1时候：[1] - 当加入
2以后：[2, 1], [1, 2] - 当加入
3以后：[3, 2, 1], [2, 3, 1], [2, 1, 3]; [3, 1, 2], [1, 3, 2], [1, 2, 3]
易错点：
- 在新建
List类型变量时要使用ArrayList或其他类型初始化，在赋值时同样。
Java 实现
public
class
Solution
{
public
List
<
List
<
Integer
>
>
permute(
int
[] nums) {
List
<
List
<
Integer
>
>
result =
new
ArrayList
<
>
();
// start from an empty list
result.add(
new
ArrayList
<
Integer
>
());
for
(
int
i =
0
; i
<
nums.length; i++) {
// list of list in current iteration of the array num
List
<
List
<
Integer
>
>
current =
new
ArrayList
<
>
();
for
(List
<
Integer
>
list : result) {
// # of locations to insert is largest index + 1
for
(
int
j =
0
; j
<
list.size() +
1
; j++) {
// + add nums[i] to different locations
list.add(j, nums[i]);
current.add(
new
ArrayList
<
Integer
>
(list));
// - remove nums[i] add
list.remove(j);
}
}
// carefull for the copy
result =
new
ArrayList
<
>
(current);
}
return
result;
}
}