感觉回溯算法就相当于DFS
一道经典题目:全排列问题:
image.png

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
    LinkedList<Integer> track  = new LinkedList<>();
    traverse(nums,track);
    return res;    
    }
    void traverse(int[] nums,LinkedList<Integer> track){
        if(track.size()==nums.length){
            res.add(new LinkedList(track)); //!!!!!!!!!!!!!这里一定要注意是写new LinkedList(track)
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(track.contains(nums[i]))continue;
            track.add(nums[i]);
            traverse(nums,track);
            track.removeLast();
        }
    }

}

这里有一点一定要注意,即代码中感叹号注释的那一块,当时做的时候写的是res.add(track);但是最后结果输出的是[[],[],[],[],[],[]]。一脸懵逼
image.png
想了一阵终于想通,java只有值传递,函数传递的是对象的引用拷贝,不管调用多少次函数,他们产生的track都指向一个对象。当刚运行到res.add(track)时存的可能是你想要的值,但是当函数运行完后,track必然会变为空列表。所以这里用new LinkedList(track)相当于对track取快照。

Q.E.D.