目標(biāo)：尋找所有可行解

解決一個(gè)回溯問題，實(shí)際上就是一個(gè)決策樹的遍歷過程

三要素

1. 路徑：也就是已經(jīng)做出的選擇。
2. 選擇列表：也就是你當(dāng)前可以做的選擇。
3. 結(jié)束條件：也就是到達(dá)決策樹底層，無法再做選擇的條件。

算法框架

result = []
def backtrack(路徑, 選擇列表):
    if 滿足結(jié)束條件:
        result.add(路徑)
        return

    for 選擇 in 選擇列表:
        做選擇
        backtrack(路徑, 選擇列表)
        撤銷選擇

1.全排列

public class Permute {

    /**
     * 結(jié)果集
     */
    private static List<List<Integer>> res = new ArrayList<>();

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums));
    }

    private static List<List<Integer>> permute(int[] nums) {
        //路徑
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    private static void backtrack(int[] nums, LinkedList<Integer> track) {
        // 路徑：記錄在 track 中
        // 選擇列表：nums 中不存在于 track 的那些元素
        // 結(jié)束條件：nums 中的元素全都在 track 中出現(xiàn)
        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]);
            //進(jìn)入下一層決策樹
            backtrack(nums, track);
            //撤銷選擇
            track.removeLast();
        }
    }
}

2.重復(fù)數(shù)組的全排列

public class PermuteUnique {
    /**
     * 標(biāo)記已經(jīng)填過的數(shù)
     */
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, perm);
        return ans;
    }

    /**
     * 回溯搜索
     * @param nums 目標(biāo)數(shù)組
     * @param ans 結(jié)果集
     * @param perm 當(dāng)前路徑
     */
    public void backtrack(int[] nums, List<List<Integer>> ans,  List<Integer> perm) {
        //結(jié)束條件
        if (perm.size() == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            //防止重復(fù)數(shù)字填入，排序后比較
            // 假設(shè)我們有 3 個(gè)重復(fù)數(shù)排完序后相鄰，那么我們一定保證每次都是拿從左往右第一個(gè)未被填過的數(shù)字，
            // 即整個(gè)數(shù)組的狀態(tài)其實(shí)是保證了
            // [未填入，未填入，未填入] 到 [填入，未填入，未填入]，
            // 再到 [填入，填入，未填入]，最后到 [填入，填入，填入] 的過程的，因此可以達(dá)到去重的目標(biāo)。
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            //選擇
            perm.add(nums[i]);
            vis[i] = true;
            //下一層回溯
            backtrack(nums, ans,  perm);
            //取消選擇
            vis[i] = false;
            perm.remove(perm.size()-1);
        }
    }
}