Permutations
Permutations ( leetcode lintcode )
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;
}
}