回溯法 - 输出自然数1到n所有不重复的排列，即n的全排列

1. 问题描述： 输出自然数1到n的所有不重复的排列，即n的全排列。

2. 问题分析：

   (1) 解空间： n的全排列是一组n元一维向量(x1, x2, x3, ... , xn),搜索空间是：1<=xi<=n i=1,2,3,...,n
  
   (2) 约束条件： xi互不相同。技巧：采用"数组记录状态信息", 设置n个元素的一维数组d，其中的n个元素用来记录数据
1~n的使用情况，已使用置1，未使用置0

3. Java代码：

package boke;

/**
 * 回溯法
 * 
 * @since jdk1.6
 * @author 毛正吉
 * @version 1.0
 * @date 2010.05.25
 * 
 */
public class NAllArrangement {
	private int count = 0; // 解数量
	private int n; // 输入数据n
	private int[] a; // 解向量
	private int[] d; // 解状态

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//测试例子
		NAllArrangement na = new NAllArrangement(5, 100);
		na.tryArrangement(1);

	}

	public NAllArrangement(int _n, int maxNSize) {
		n = _n;
		a = new int[maxNSize];
		d = new int[maxNSize];
	}

	/**
	 * 处理方法
	 * 
	 * @param k
	 */
	public void tryArrangement(int k) {
		for (int j = 1; j <= n; j++) { // 搜索解空间
			if (d[j] == 0) {
				a[k] = j;
				d[j] = 1;
			} else { // 表明j已用过
				continue;
			}

			if (k < n) { // 没搜索到底
				tryArrangement(k + 1);
			} else {
				count++;
				output(); // 输出解向量
			}
			d[a[k]] = 0; // 回溯
		}
	}

	/**
	 * 输出解向量
	 */
	private void output() {
		System.out.println("count = " + count);
		for (int j = 1; j <= n; j++) {
			System.out.print(a[j] + " ");
		}
		System.out.println("");
	}

}