回溯法求全排列问题

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import org.junit.Test;

public class Permutation {
	public static final int nums[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	public boolean isVisit[] = new boolean[nums.length];

	public void doPermutation(int index, Stack<Integer> list) {		//循环退出条件
		if (nums.length == index) {
			System.out.println(list);
			return;
		}
		//回溯法关键代码 相互影响的要使用一个结构体保存访问过的变量
		for (int i = 0; i < nums.length; i++) {
			if (!isVisit[i]) {
				isVisit[i] = true;
				list.push(nums[i]);
				doPermutation(index + 1, list);
				isVisit[i] = false;
				list.pop();
			}

		}
		return;
	}

	@Test
	public void testPer() {
		doPermutation(0, new Stack<Integer>());
	}
}


本站运行时间: 0天 0小时 00分00秒

Copyright © 2020 过去的,未来的

Powered by Halo • Theme by Subtle Galaxy • REFERENCE FROM 寒山

Back to the top