1. 回溯法 - dfs(sort 后, 然后 dfs, 数列是按字典序的)
- import java.util.Arrays;
- import java.util.Scanner;
- public class Main {
- static int n;
- static final int max=1005;
- static boolean vis[]=new boolean [max];
- static int a[]=new int[max];
- static int b[]=new int[max];
- public static void dfs(int step){
- if(step==n){
- for(int i=0;i<n;i++) System.out.print(b[i]);
- System.out.println();
- }
- for(int i=0;i<n;i++){
- if(!vis[i]){
- vis[i]=true;
- b[step]=a[i];
- dfs(step+1);
- vis[i]=false;
- }
- }
- }
- public static void main(String[] args) {
- Scanner scan=new Scanner(System.in);
- n=scan.nextInt();
- for(int i=0;i<n;i++) a[i]=scan.nextInt();
- Arrays.sort(a,0,n);
- dfs(0);
- }
- }
2. 递归法 (不按字典序)
- import java.util.Arrays;
- public class Main {
- public static void print(int arr[],int n){
- for(int i=0;i<=n;i++)
- System.out.print(arr[i]);
- System.out.println();
- }
- public static void swap(int arr[],int i,int p){
- int t=arr[i];
- arr[i]=arr[p];
- arr[p]=t;
- }
- public static void allSort(int arr[],int p,int q){
- if(p==q){
- print(arr,q);
- }
- else{
- for(int i=p;i<=q;i++){
- swap(arr,i,p);
- allSort(arr,p+1,q);
- swap(arr,i,p);
- }
- }
- }
- public static void main(String[] args) {
- int arr[]={1,2,3,4};
- Arrays.sort(arr,0,arr.length);
- allSort(arr,0,arr.length-1);
- }
- }
全排列模板
来源: http://www.bubuko.com/infodetail-3383008.html