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].
數(shù)組全排列題目，基本思想是對每一個字符與后面的字符作交換，以生成新的序列。為了防止重復(fù)，交換之前需要檢查之前是否已經(jīng)和同樣的字符串做過交換。代碼如下：
1 public class PermutationsII {
2 public ArrayList<ArrayList<Integer>> permuteUnique(
int[] num) {
3 ArrayList<ArrayList<Integer>> result =
new ArrayList<ArrayList<Integer>>();
4 permuteUnique(num, 0, result);
5 return result;
6 }
7 8 void permuteUnique(
int[] num,
int begin,
9 ArrayList<ArrayList<Integer>> result) {
10 if (begin > num.length - 1) {
11 ArrayList<Integer> item =
new ArrayList<Integer>();
12 for (
int h = 0; h < num.length; h++) {
13 item.add(num[h]);
14 }
15 result.add(item);
16 }
17 for (
int end = begin; end < num.length; end++) {
18 if (isSwap(num, begin, end)) {
19 swap(num, begin, end);
20 permuteUnique(num, begin + 1, result);
21 swap(num, begin, end);
22 }
23 }
24 }
25 26 boolean isSwap(
int[] arr,
int i,
int j) {
27 for (
int k = i; k < j; k++) {
28 if (arr[k] == arr[j]) {
29 return false;
30 }
31 }
32 return true;
33 }
34 35 private void swap(
int[] a,
int i,
int j) {
36 int tmp = a[i];
37 a[i] = a[j];
38 a[j] = tmp;
39 }
40 }