题目

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; } }