Leetcode024--递归打印全排列

一、原题



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]


一、中文


返回一个数组的所有排列



三、举例



123的排列分别有123,132,213,231,312,321


四、思路



首先我想到的也是使用递归的方式,也是逐个递减的递归方式,但是是没有想到使用交换的方式,这样每次都要构建一个新的比上一个少一个元素的数组,显然这种方式的效率不高而且很难实现,我们应该使用的是如下的交换的方式,其实很多的这种问题都是可以通过交换的方式来解决的。



五、程序


public class LeetCode27{
	public static void main(String args[]){
		int num[] = new int[]{1, 2, 3};
		arrayAllNum(num, 0, num.length-1);
	}
	
	//递归是通过递归交换的方式,最后一次将递归交换的结果全部进行打印
	public static void arrayAllNum(int num[], int begin, int end){
		if(end == begin){//一到递归的出口就输出数组
			for(int i = 0; i <= end; i++){
				System.out.print(num[i]+" ");
			}
			System.out.println();
		}else{
			//不是最后一次就逐个进行交换的递归
			for(int j = begin; j <= end; j++){
				swap(num, begin, j);
				arrayAllNum(num, begin+1, end);
				swap(num, begin, j);
			}
		}
	}
	
    public static void swap(int arr[], int i1, int i2) {  
        int temp = arr[i2];  
        arr[i2] = arr[i1];  
        arr[i1] = temp;  
    }  
	
}

------------------------outpu---------------------------

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 2 1 
3 1 2 
无觅关联推荐,快速提升流量
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。