回溯法求全排列问题

过去的,未来的
2020-01-04 / 0 评论 / 0 点赞 / 910 阅读 / 0 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2020-01-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
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

评论区