Permutations

Given a collection of distinct 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].

``````import java.util.*;
/**
* Created by gzdaijie on 16/5/22
* 递归解法
*/
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
boolean[] flag = new boolean[nums.length];
ArrayList<Integer> tmp = new ArrayList<Integer>();
permuteRecursion(result, nums, tmp, flag);
return result;
}

public void permuteRecursion(List<List<Integer>> result, int[] nums, ArrayList<Integer> tmp, boolean[] flag) {
int len = nums.length;

if (tmp.size() == len) {
result.add((List<Integer>) tmp.clone());
return;
}

for (int i = 0; i < len; i++) {
if (!flag[i]) {
flag[i] = true;
tmp.add(nums[i]);
permuteRecursion(result, nums, tmp, flag);
tmp.remove(tmp.size() - 1);
flag[i] = false;
}
}
}
}
``````
``````import java.util.*;
/**
* Created by gzdaijie on 16/5/22
* 交换递归解法
*/
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
permuteRecursion(nums, result, 0);
return result;
}

private void swap(int[] nums, int a, int b) {
if (nums[a] != nums[b]) {
int t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}

private void permuteRecursion(int[] nums, List<List<Integer>>result, int index) {
int len = nums.length;
if (index == len - 1) {
List<Integer> tmp = new ArrayList<>();
for (int i = 0; i < len; tmp.add(nums[i++])); /* empty */
result.add(tmp);
return;
}

for (int i = index; i < len; i++) {
swap(nums, index, i);
permuteRecursion(nums, result, index + 1);
swap(nums, i, index);
}
}
}
``````
updated 2016-05-22 21:53:55