思路：

For example：

123的全排列=

1在最前面 23的全排列

+

2在最前面 13的全排列

+

3最前面 12的全排列

所以只需交换和最前面元素的位置，生成剩余元素的全排列即可。

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int a[]=new int[n];
		for(int i=1;i<=n;i++) {
			a[i-1]=i;
		}
		dfs(a,0,n-1);
	}

	private static void dfs(int a[],int s,int e) {
		if(s==e) {
			for(int i=0;i<a.length;i++)
				System.out.print(a[i]+" ");
			System.out.println();
			
		}
		else
			for(int i=s;i<=e;i++) {
				swap(a,s,i);
				dfs(a,s+1,e);
				swap(a,s,i);
			}

	}
	private static void swap(int[] a, int s2, int i) {
		// TODO Auto-generated method stub
		int t=a[s2];
		a[s2]=a[i];
		a[i]=t;
	}

}