”回溯算法“框架及练习题

”回溯算法“框架及练习题

结论:回溯 = 穷举
解决一个回溯问题,实际上就是一个决策树的遍历过程

  1. 路径:就是已经做出的选择
  2. 选择列表:就是你当前可以做出的选择
  3. 结束条件:就是base case条件,也就是临界条件

框架如下:

result = []
def backtrack(路径,选择列表) {
	if 满足结束条件 : 
		result.add(路径)
		return
	for 选择 in 选择列表
		做选择
		backtrack(路径,选择列表)
		撤销选择	
}

举例:经典回溯算法问题:全排列问题

public class TestNode {
	private static List<List<Integer>> res = new LinkedList<>();

	public static void main(String[] args){
			//问题2.1:全排列问题
	        permute(new int[]{1,2,3});
	        res.stream().forEach(item -> System.out.print(item + " "));
	}	
	/**
     * 问题2.1:全排列问题,输入一个数组,输出所有全排列顺序
     *      框架:路径:记录在track中
     *           选择列表:nums中不存在于track的那些元素
     *           结束条件:nums中元素全部在track中出现
     * @param nums 数组
     * @return list
     */
    public static List<List<Integer>> permute(int[] nums) {
        //记录“路径”
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }
    public static void backtrack(int[] nums, LinkedList<Integer> track) {
        //base case
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            //排除不合法的选择
            if (track.contains(nums[i])) continue;
            //做选择
            track.add(nums[i]);
            //进入下一层决策树
            backtrack(nums, track);
            //取消选择
            track.removeLast();
        }
    }

输出结果

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] 
上一篇:计算机网络--接入互联网方式


下一篇:回溯和动态规划