題目

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

思路

這道題是個遞歸題。先來講講思路:

當你只有1個數的時候，那麼它的全排列就是它本身

假設你有2個數字 (1,2) 那麼它的全排列是多少呢？分別是以 1 開頭 和 2 開頭的2中情況吧。即(1,2),(2,1)

假設你有3個數字 (1,2,3)那麼它的全排列是多少呢？分別是以 1開頭(配上2和3的排列)和以2開頭(配上1和3的排列)和以3開頭(配上1和2的排列)的3大種情況吧。即(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1)

假設你有有4個數字(1,2,3,4),那麼它的全排列是多少呢？分別是以1開頭(配上2和3和4的排列)和以2開頭(配上1和3和4的排列)和以3開頭(配上1和2和4的排列)和以4開頭(配上1和2和3的排列)的4種情況吧..太多了就不寫了

以此類推..

好了結束

代碼

public class Solution {
	public void swap(int[] a,int p1,int p2)
	{
		int temp = a[p1];		
		a[p1] = a[p2];
		a[p2] = temp;
	}
	
	public void Permutations(int[] num ,int begin, int end, ArrayList> result )
	{
		if(begin>end)
		{
			ArrayList temp = new ArrayList();
			for(int i = 0 ;i <= end; i ++)
			{
				temp.add(num[i]);
			}
			result.add(temp);
		}
		else
		{			
			for(int i = begin; i <=end ; i++)
			{
				swap(num,begin,i);
				Permutations(num,begin+1,end,result);
				swap(num,begin,i);
			}
		}
	}
			
	
    public ArrayList> permute(int[] num) 
    {
        ArrayList> result = new ArrayList>();
        
        if( num.length == 0 )
        	return result;
        Permutations(num,0,num.length-1,result);
        return result;
    }
}