全排列算法之回溯求解_全排列问题回溯算法

 全排列算法回溯实现，重点就在回溯上，只有十分了解回溯的实现原理和工作过程，才能真正掌握回溯算法。

在全排列中，依次将数组的从0到N提到数组的头，再将后面的1-N进行全排列，重点在回溯时，要将之前交换的两个元素再换回来，将数组还原，以免影响下次循环交换。

废话不多数，上代码。

public class Main {
	static int ans=0;//总的排列组合数目
	
	static int[] arr= {1,2,3,4};//要排列的数组
	
	public static void main(String[] args) throws Exception {
		
		perm(arr,0,(arr.length-1));//调用排列函数
		
		System.out.println(ans);//输出总的排列组合数目
	}
	/**
	 * 排列函数
	 * @param arr 要排列的数组
	 * @param start 要排列的数组的起始位置  即从下标为start开始排列
	 * @param end 从数组的下标为start到end结束进行排列
	 */
	public static void perm(int[] arr,int start,int end) {
		//排列前先判断，
		//如果开始排列的下标和结束的下标一致，说明只排列一个数字，即此次排列完成，需要回溯进行下一次排列
		if(start == end) {
			print();//打印本次排列的 
			return;//回溯
		}else {
			//for循环同理从start开始，到end结束
			/** 
			 *  1,2,3,4—>swap(0,0)—>1 [2 3 4] (子递归先不管)—>swap(0,0)—>1,2,3,4
				1,2,3,4—>swap(0,1)—>2 [1 3 4] (子递归先不管)—>swap(0,1)—>1,2,3,4
				1,2,3,4—>swap(0,2)—>3 [2 1 4] (子递归先不管)—>swap(0,2)—>1,2,3,4
				1,2,3,4—>swap(0,3)—>4 [2 3 1] (子递归先不管)—>swap(0,3)—>1,2,3,4
				..............
				1,2...N—>swap(0,N)—>N [2 3...N-1,1] (子递归先不管)—>swap(0,N)—>1,2,3,4
				每次递归完回溯时，要通过再次swap交换，将之前交换的元素还原（以免影响下一次循环），才能进行下一次循环
			 */
			for (int j = start; j <=end; j++) {
				swap(arr, start, j);//将元素提到数组头
				perm(arr,start+1,end);//将剩下的数组再进行排列
				swap(arr, start, j);//将前面交换的元素换回来，将数组还原，在进行下一次循环排列
			}
		}
	}
	//交换函数
	public static void swap(int[] arr,int i,int j) {
		int temp=arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	//打印一次排列结果
	private static void print() {
		ans++;//解法数+1
		for (int i =0 ; i < arr.length -1 ; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
}