全排列的递归实现

概述

全排列在很多竞赛题中会经常用到，因为只有枚举出数组中元素的所有可能的组合情况，才能进行题目的下一步操作，那么这篇文章就用递归的思想来实现全排列。

首先我们先举一个最简单的全排列的例子，给出数组{1,2,3}，那么这个数组的全排列就有6种情况：

{1,2,3}  {1,3,2}  {2,1,3}  {2,3,1} {3,1,2} {3,2,1}

通过递归可以轻松的实现全排列。

全排列的实现

import java.util.Arrays;

public class DemoTest {
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3 };
		f(0, arr);
	}

	//进行全排列
	private static void f(int k, int[] arr) {
		if (k == arr.length) {
			System.out.println(Arrays.toString(arr));
			return;
		}

		for (int i = k; i < arr.length; i++) {
			int t=arr[k];
			arr[k]=arr[i];
			arr[i]=t;
			
			f(k+1,arr);
			
			t=arr[k];
			arr[k]=arr[i];
			arr[i]=t;
		}
	}
}