Permutations
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].
SOLUTION 1:
经典的递归回溯题目，一次ACCEPT. 请也参考上一个题目LeetCode: Combinations 解题报告.
public class Solution {
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (num == null || num.length == 0) {
return ret;
}
dfs(num, new ArrayList<Integer>(), ret);
return ret;
}
public void dfs(int[] num, List<Integer> path, List<List<Integer>> ret) {
int len = num.length;
if (path.size() == len) {
ret.add(new ArrayList<Integer>(path));
return;
}
for (int i = 0; i < len; i++) {
if (path.contains(num[i])) {
continue;
}
path.add(num[i]);
dfs(num, path, ret);
path.remove(path.size() - 1);
}
}
}
SOLUTION 2:
可能有的同学觉得为什么path.contains不用hashmap来代替哩？所以主页君写了一个带hashmap的版本。结论是，在这个set规模小的时候，hashmap的性能还不
如arraylist。
原因可能在于，hashmap申请的不是一个连续的空间，而arraylist比较小的话，直接在连续内存中操作，速度会比较快。
以下是此程序的运行结果，hashmap的版本速度要慢一倍：
Test size:9
Computing time with HASHMAP: 629.0 millisec.
Test size:9
Computing time with list: 310.0 millisec.
package Algorithms.permutation; import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashMap; public class Permutation {
public static void main(String[] strs) {
int[] num = {1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.printf("Test size:%d \n", num.length); Stopwatch timer1 = new Stopwatch(); permute(num);
System.out
.println("Computing time with HASHMAP: "
+ timer1.elapsedTime() + " millisec."); System.out.printf("Test size:%d \n", num.length); Stopwatch timer2 = new Stopwatch(); permute2(num);
System.out
.println("Computing time with list: "
+ timer2.elapsedTime() + " millisec.");
} public static ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
if (num == null) {
return ret;
} permuteHelp(num, ret, new LinkedHashMap<Integer, Integer>());
return ret;
} public static void permuteHelp(int[] num, ArrayList<ArrayList<Integer>> ret, LinkedHashMap<Integer, Integer> set) {
if (set.size() == num.length) { ArrayList<Integer> list = new ArrayList<Integer>();
for (Integer i: set.keySet()){
list.add(i);
}
ret.add(list);
return;
} int len = num.length;
for (int i = 0; i < len; i++) {
if (set.containsKey(num[i])) {
continue;
} //path.add(num[i]);
set.put(num[i], 0);
permuteHelp(num, ret, set);
//path.remove(path.size() - 1);
set.remove(num[i]);
}
} public static ArrayList<ArrayList<Integer>> permute2(int[] num) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
if (num == null) {
return ret;
} ArrayList<Integer> path = new ArrayList<Integer>();
permuteHelp2(num, path, ret);
return ret;
} public static void permuteHelp2(int[] num, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> ret) {
if (path.size() == num.length) {
ret.add(new ArrayList<Integer>(path));
return;
} int len = num.length;
for (int i = 0; i < len; i++) {
if (path.contains(num[i])) {
continue;
} path.add(num[i]);
permuteHelp2(num, path, ret);
path.remove(path.size() - 1);
}
}
}
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dfs/Permute.java