Permutations (Java)

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].

	/*
	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].
	*/
	// Best Time O(n!)
	// space efficence solution
	public class Solution {
	public ArrayList<ArrayList<Integer>> permute(int[] num) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num==null || num.length==0){
	return result;
	}
	// record is currenct num already be used
	boolean[] used=new boolean[num.length];
	ArrayList<Integer> current=new ArrayList<Integer>();
	int index=0;
	buildResult(num, index, current,used, result);
	return result;
	}
	public void buildResult(int[] num, int index, ArrayList<Integer> current, boolean[] used, ArrayList<ArrayList<Integer>> result){
	if (index==num.length){
	result.add(new ArrayList<Integer>(current));
	return;
	}
	for (int i=0; i<num.length;i++){
	if (!used[i]){
	current.add(num[i]);
	used[i]=true;
	buildResult(num, index+1, current, used, result);
	used[i]=false;
	current.remove(current.size()-1);
	}
	}
	}
	}
	// same time complexity with above but cost more space
	public class Solution {
	public ArrayList<ArrayList<Integer>> permute(int[] num) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (num==null || num.length==0){
	return result;
	}
	for(int i=0; i<num.length; i++){
	result=buildResult(num[i], result );
	}
	return result;
	}
	private ArrayList<ArrayList<Integer>> buildResult(int num, ArrayList<ArrayList<Integer>> result){
	if (result.isEmpty()){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	temp.add(num);
	result.add(temp);
	return result;
	}
	ArrayList<ArrayList<Integer>> newResult=new ArrayList<ArrayList<Integer>> ();
	for (ArrayList<Integer> al: result){
	for (int i=0; i<=al.size(); i++){
	ArrayList<Integer> temp=new ArrayList<Integer>(al);
	temp.add(i, num);
	newResult.add(temp);
	}
	}
	return newResult;
	}
	}

view raw Permutations.java hosted with ❤ by GitHub