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

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]