總結(jié)

解決一個回溯問題，實際上就是一個決策樹的遍歷過程。你只需要思考 3 個問題：
1、路徑：也就是已經(jīng)做出的選擇。
2、選擇列表：也就是你當前可以做的選擇。
3、結(jié)束條件：也就是到達決策樹底層，無法再做選擇的條件。

代碼方面，回溯算法的框架：

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

全排列

給定一個 沒有重復 數(shù)字的序列，返回其所有可能的全排列。
示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

回溯算法1：
路徑：ArrayList<Integer> per，包含所有整數(shù)（不重復）的集合就是一條路徑；
選擇列表：nums和tags決定，所有未選擇過的整數(shù)，都可以選擇；
結(jié)束條件：per中的整數(shù)個數(shù)達到最大；
第一種算法的缺點為需要額外的tags來標識nums中的整數(shù)是否已經(jīng)被選擇過，第二種則不需要。時間負責度為。

public static List<List<Integer>> permute2(int[] nums) {

        List<List<Integer>> pers = new ArrayList<>();
        ArrayList<Integer> per = new ArrayList<>();

        boolean[] tags = new boolean[nums.length];

        backtrack2(pers, per, nums, tags);

        return pers;
    }

    public static void backtrack2(List<List<Integer>> pers, ArrayList<Integer> per, int[] nums, boolean[] tags) {

        if (per.size() == nums.length) {
            pers.add(new ArrayList<>(per));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if(!tags[i]){
                per.add(nums[i]);
                tags[i] = true;
                backtrack2(pers, per, nums, tags);
                per.remove(per.size()-1);
                tags[i] = false;
            }
        }

    }

回溯算法2：
將這個問題可以看作有 n 個的空格，我們需要從左往右依此填入題目給定的 n 個數(shù)，每個數(shù)只能使用一次。為了在選擇下一個填入的數(shù)時不重復，我們需要將已經(jīng)填過的數(shù)放在數(shù)組的左邊，未填的數(shù)放在數(shù)組的右邊。
具體來說，假設(shè)我們已經(jīng)填到第 pos 個位置，那么nums[] 數(shù)組中 [0, pos?1] 是已填過的數(shù)的集合，[pos , n?1] 是待填的數(shù)的集合。我們肯定是嘗試用 [pos, n?1] 里的數(shù)去填第 pos 個數(shù)，假設(shè)待填的數(shù)的下標為 i ，那么填完以后我們將第 i 個數(shù)和第 pos 個數(shù)交換，即能使得在填第 pos 個數(shù)的時候 nums[] 數(shù)組的[0,pos ] 部分為已填過的數(shù)，[pos +1,n?1] 為待填的數(shù)，回溯的時候交換回來即能完成撤銷操作。

public class Solution {

    private List<List<Integer>> ans;
    private int[] nums;

    public List<List<Integer>> permuteUnique(int[] nums) {

        this.ans = new ArrayList<>();
        this.nums = nums;

        List<Integer> path = new ArrayList<>();
        for (int num : nums) {
            path.add(num);
        }

        backtrack(path, 0);

        return ans;
    }

    public void backtrack(List<Integer> path, int pos) {
        if (pos == nums.length - 1) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = pos; i < nums.length; i++) {
            Collections.swap(path, i, pos);
            backtrack(path, pos + 1);
            Collections.swap(path, i, pos);
        }
    }
    
}

全排列 II

為了去重，需要先排序；當相鄰兩個數(shù)相同，且前一個數(shù)剛剛被撤銷（即visit=false），這種情況下會導致重復的排列，需要剪枝。

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if(nums.length == 0){
            return ans;
        }
        // 排序是去重的前提
        Arrays.sort(nums);
        backtrace(ans, new ArrayList<>(nums.length), nums, new boolean[nums.length]);
        return ans;
    }

    public void backtrace(List<List<Integer>> ans, List<Integer> path, int[] nums, boolean[] visit) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1]) {
                continue;
            }
            if (!visit[i]) {
                visit[i] = true;
                path.add(nums[i]);
                backtrace(ans, path, nums, visit);
                visit[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

交換去重
交換去重不需要提前排序，也不需要額外的visit數(shù)組，所以推薦使用此種方式進行全排列問題的求解。

public class Solution {
    private List<List<Integer>> ans;
    private int[] nums;

    public List<List<Integer>> permuteUnique(int[] nums) {

        this.ans = new ArrayList<>();
        this.nums = nums;

        List<Integer> path = new ArrayList<>();
        for (int num : nums) {
            path.add(num);
        }

        backtrack(path, 0);

        return ans;
    }

    public void backtrack(List<Integer> path, int pos) {
        if (pos == nums.length - 1) {
            ans.add(new ArrayList<>(path));
            return;
        }

        Set<Integer> set = new HashSet<>();
        for (int i = pos; i < nums.length; i++) {
            // 去重，在給pos位置賦值時，如果前面已經(jīng)有過相同的數(shù)被賦值給pos，那么就過濾
            if(set.contains(path.get(i))){
                continue;
            }
            set.add(path.get(i));

            Collections.swap(path, i, pos);
            backtrack(path, pos + 1);
            Collections.swap(path, i, pos);
        }
    }
}

火柴拼正方形

還記得童話《賣火柴的小女孩》嗎？現(xiàn)在，你知道小女孩有多少根火柴，請找出一種能使用所有火柴拼成一個正方形的方法。不能折斷火柴，可以把火柴連接起來，并且每根火柴都要用到。

輸入為小女孩擁有火柴的數(shù)目，每根火柴用其長度表示。輸出即為是否能用所有的火柴拼成正方形。

示例 1:
輸入: [1,1,2,2,2]
輸出: true
解釋: 能拼成一個邊長為2的正方形，每邊兩根火柴。

求解：
1）相當于把所有的物體（火柴）往4個容量一樣（正方形邊長）的容器里放，最后所有的物體都放入容器中，且每個容器剛好滿，則成功；
2）對于每個物體往哪個容器里放，依次遍歷即可；如果可以放入該容器，并且可以導致最后的成功，則返回true；否則，放入下一個容器中。
3）如果火柴全部放完，此時如果四個容器大小一致，那么則成功；其實只要全部火柴放置完，根據(jù)前面的條件，此時四個容器大小必然一致；
4）先對火柴排序，從大數(shù)開始放，可以減少回溯的次數(shù)；類似于裝箱問題的貪婪解法，先放置大體積的物品容易成功。
算法復雜度為。

public static boolean makesquare(int[] nums){

        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum % 4 != 0){
            return false;
        }
        int edgeLen = sum / 4;
        if(edgeLen <= 0){
            return false;
        }

        // 排序后從大數(shù)開始裝桶, 會減少回溯次數(shù); 類似裝箱問題中, 先裝體積大的物品
        Arrays.sort(nums);
        int[] buckets = new int[4];
        return dfs(nums.length-1, nums, edgeLen, buckets);
    }

    public static boolean dfs(int ind, int[] nums, int len, int[] buckets){

        if(ind < 0){
            // return true; // 也正確
            return buckets[0] == len && buckets[1] == len && buckets[2] == len && buckets[3] == len;
        }

        for(int i = 0; i<4; i++){
            if(buckets[i] + nums[ind] > len){
                continue;
            }
            buckets[i] += nums[ind];
            if(dfs(ind-1, nums, len, buckets)){
                return true;
            }
            buckets[i] -= nums[ind];
        }

        return false;
    }

單詞拆分

給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現(xiàn)的單詞。

說明：

拆分時可以重復使用字典中的單詞。
你可以假設(shè)字典中沒有重復的單詞。
示例 1：
輸入: s = "leetcode", wordDict = ["leet", "code"]
輸出: true
解釋: 返回 true 因為 "leetcode" 可以被拆分成 "leet code"。
示例 2：
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因為 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重復使用字典中的單詞。
示例 3：
輸入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出: false

記憶化回溯（記錄子問題的解，避免重復計算）
我們可以使用記憶化的方法，其中一個 memo數(shù)組會被用來保存子問題的結(jié)果。每當訪問到已經(jīng)訪問過的后綴串，直接用 memo數(shù)組中的值返回而不需要繼續(xù)調(diào)用函數(shù)。
通過記憶化，許多冗余的子問題可以極大被優(yōu)化，回溯樹得到了剪枝，因此極大減小了時間復雜度。
時間復雜度；空間復雜度

public static boolean wordBreak(String s, List<String> wordDict) {
        Boolean[] results = new Boolean[s.length()];
        return dfs(s, wordDict, 0, results);
    }

    public static boolean dfs(String s, List<String> wordDict, int start, Boolean[] result){

        if(start == s.length()){
            return true;
        }

        if(result[start] != null){
            return result[start];
        }

        for(int end = start + 1; end <= s.length(); end++){
            if(wordDict.contains(s.substring(start, end)) && dfs(s, wordDict, end, result)){
                result[start] = true; // 記錄答案, 以免重復計算子問題
                return true;
            }
        }

        result[start] = false;// 記錄答案, 以免重復計算子問題
        return false;
    }

組合總和

回溯（剪枝）
1）避免重復，需要設(shè)置一個起始下標start；
2）path全局只有一個引用，所以加入ans時需要new新對象。

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        backtrace(ans, new ArrayList<>(), candidates, 0, target, 0);
        return ans;
    }

    public void backtrace(List<List<Integer>> ans, List<Integer> path, int[] candidates, int sum, int target, int start) {
        if (sum == target) {
            ans.add(new ArrayList<>(path));
        }

        // 剪枝
        if (sum > target) {
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            // 剪枝
            if (sum + candidates[i] > target) {
                break;
            }

            // 選擇
            sum += candidates[i];
            path.add(candidates[i]);
            // 回溯
            backtrace(ans, path, candidates, sum, target, i);
            sum -= candidates[i];
            // 撤銷選擇
            path.remove(path.size() - 1);
        }

        return;
    }

組合總和 II

回溯解法
1）先不考慮任何剪枝的代碼，按照回溯框架寫出回溯代碼；
2）利用提前排序，進行各種剪枝；

private int[] candidates;
    private List<List<Integer>> ans;
    private int target;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        this.ans = new ArrayList<>();
        this.target = target;
        this.candidates = candidates;

        if(candidates.length == 0){
            return ans;
        }

        Arrays.sort(candidates);
        backtrace(new ArrayList<>(), 0, 0);
        return ans;
    }

    public void backtrace(List<Integer> integers, int sum, int k) {
        if (sum == target) {
            List<Integer> list = new ArrayList<>(integers);
            ans.add(list);
            return;
        }

        // 剪枝
        if(sum > target){
            return;
        }

        for (int i = k; i < candidates.length; i++) {

            // 剪枝
            if(sum + candidates[i] > target){
                break;
            }

            // 剪枝
            if(i > k && candidates[i] == candidates[i-1]){
                continue;
            }

            integers.add(candidates[i]);
            backtrace(integers, sum + candidates[i], i + 1);
            integers.remove(integers.size() - 1);
        }

    }

}

電話號碼的字母組合

給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

示例:
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
說明:
盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。

回溯

private static String[] cc = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public static List<String> letterCombinations(String digits) {

        if(digits.length() == 0){
            return new ArrayList<>();
        }

        List<String> ret = new ArrayList<>();

        List<String> words = new ArrayList<>();
        for(int i=0; i<digits.length(); i++){
            int index = digits.charAt(i) - '0';
            words.add(cc[index]);
        }

        backtrace(ret, new ArrayList<>(), words, 0);
        return ret;
    }

    public static void backtrace(List<String> ret, List<Character> comb, List<String> words, int wordInd){

        if(wordInd > words.size()-1){
            ret.add(listToString(comb));
            return;
        }

        String word = words.get(wordInd);
        for(int i=0; i<word.length(); i++){
            comb.add(word.charAt(i));
            backtrace(ret, comb, words, wordInd+1);
            comb.remove(comb.size()-1);
        }
    }

    public static String listToString(List<Character> comb){
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<comb.size(); i++){
            sb.append(comb.get(i));
        }
        return sb.toString();
    }

復原IP地址

    public static List<String> restoreIpAddresses(String s) {
        List<String> ips = new ArrayList<>();
        backtrace(ips, s, new ArrayList<>(), 0);
        return ips;
    }

    public static void backtrace(List<String> ips, String s, List<String> segs, int sInd){

        if(segs.size() ==  4){
            if(sInd == s.length()){
                ips.add(String.join(".", segs));
            }
            return;
        }

        for(int end = sInd + 1; end <= sInd + 3 && end <= s.length(); end++){

            String ipSeg = s.substring(sInd, end);

            // 剪枝
            int leftLength = s.length() - end;
            int leftCount = 4 - segs.size() - 1;
            if(leftLength < leftCount || leftLength > leftCount * 3){
                continue;
            }

            // 三位數(shù)不能超過255
            if(end == sInd + 3 && ipSeg.compareTo("255") > 0){
                break;
            }

            // 二位數(shù)/三位數(shù)不能以0開頭
            if(end > sInd + 1 && ipSeg.startsWith("0")){
                break;
            }

            segs.add(ipSeg);
            backtrace(ips, s, segs, end);
            segs.remove(segs.size()-1);
        }

    }

括號生成

回溯算法
剪枝：
1）左括號可選條件：只要左括號還有剩余，就可以選擇；
2）有括號可選條件：目前已經(jīng)選擇的左括號的數(shù)量大于右括號的數(shù)量，所以需要兩個變量分別保存已經(jīng)選擇的左括號的數(shù)量和右括號的數(shù)量。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }

        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open+1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close+1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

路徑總和 II

    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> paths = new ArrayList<>();
        if(root == null){
            return paths;
        }
        List<Integer> path = new ArrayList<>();
        path.add(root.val);
        dfs(paths, path, sum, root.val, root);
        return paths;
    }

    public static void dfs(List<List<Integer>> paths, List<Integer> path, int target, int sum, TreeNode root){

        if(sum == target && root.left == null && root.right == null){
            paths.add(new ArrayList<>(path));
            return;
        }

        if(root.left != null){
            sum += root.left.val;
            path.add(root.left.val);
            dfs(paths, path, target, sum, root.left);
            sum -= root.left.val;
            path.remove(path.size()-1);
        }

        if(root.right != null){
            sum += root.right.val;
            path.add(root.right.val);
            dfs(paths, path, target, sum, root.right);
            sum -= root.right.val;
            path.remove(path.size()-1);
        }
    }

路徑總和 III

• 前綴和：題中所求部分路徑之和 = 全部路徑之和 - 前綴路徑之和；即 target = pathSum - prefixSum；所以遍歷到當前節(jié)點時，只需判斷截止到當前節(jié)點的pathSum ?= target + prefixSum?？紤]到前綴和可能有相同值，所以需要記錄數(shù)量。
• 回溯：回到當前層時，需要恢復前綴和Map。

    private int count;

    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        count = 0;
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);
        backtrace(root, prefixSumCount, 0, sum);
        return count;
    }

    public void backtrace(TreeNode node, Map<Integer, Integer> prefixSumCount, int pathSum, int target){
        if(node == null){
            return;
        }

        pathSum += node.val;
        count += prefixSumCount.getOrDefault(pathSum - target, 0);
        prefixSumCount.put(pathSum, prefixSumCount.getOrDefault(pathSum, 0) + 1);

        backtrace(node.left, prefixSumCount, pathSum, target);
        backtrace(node.right, prefixSumCount, pathSum, target);

        prefixSumCount.put(pathSum, prefixSumCount.get(pathSum) - 1);
    }

組合

回溯

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrace(ans, new ArrayList<>(), n, 0, k);
        return ans;
    }

    public void backtrace(List<List<Integer>> ans, List<Integer> path, int n, int num, int k){
        if(path.size() == k){
            ans.add(new ArrayList<>(path));
            return;
        }
        // 剪枝:當后面所有的數(shù)的個數(shù)都加入path，仍然小于k個，可以返回
        if(k - path.size() > n - num){
            return;
        }

        for(int i = num + 1; i <= n; i ++){
            path.add(i);
            backtrace(ans, path, n, i, k);
            path.remove(path.size()-1);
        }
    }

安卓系統(tǒng)手勢解鎖

回溯
1）列舉出下一步棋可能的方向：總共8組，16個方向；容易漏掉馬字格的8個方向。

    由數(shù)字得到位置: num => [(num-1)/3][(num-1)%3]
    由位置得到數(shù)字: [i][j] => i * 3 + j + 1;

4）利用對稱進行優(yōu)化，本題從1開始的手勢總數(shù)和從3,7,9開始是一樣的；從2開始的手勢總數(shù)和從4,6,8開始是一樣的；剩下最后一種從5開始的。

public class Solution {

    private int total;

    // 16 個方向
    public static int[][] directions = {
            {0, 1}, {0, -1},
            {1, 0}, {-1, 0},
            {1, 1}, {-1, -1},
            {-1, 1}, {1, -1},
            {1, 2}, {-1, -2},
            {2, 1}, {-2, -1},
            {-1, 2}, {2, -1},
            {1, -2}, {-2, 1}};
    
    public int numberOfPatterns(int m, int n) {
        int ans = 0;
        ans += getNumberOfPatterns(1, m, n) * 4; // 1,3,7,9
        ans += getNumberOfPatterns(2, m, n) * 4; // 2,4,6,8
        ans += getNumberOfPatterns(5, m, n); // 5
        return ans;
    }

    public int getNumberOfPatterns(int start, int m, int n){
        total = 0;
        boolean[] visit = new boolean[10];
        visit[start] = true;
        backtrace(1, start, visit, m, n);
        return total;
    }

    public void backtrace(int currentCount, int currentNum, boolean[] visit,  int m, int n) {

        if (currentCount >= m && currentCount <= n) {
            total++;
        }

        if (currentCount >= n) {
            return;
        }

        int currentRow = (currentNum - 1) / 3;
        int currentCol = (currentNum - 1) % 3;

        for (int[] direction : directions) {
            int nextRow;
            int nextCol;
            int tempRow = currentRow;
            int tempCol = currentCol;
            // 確定這個方向上是否有滿足條件的下一個落腳點
            boolean hasNextPos = true;
            while (true){
                nextRow = tempRow + direction[0];
                nextCol = tempCol + direction[1];
                if(nextRow >= 0 && nextRow <= 2 && nextCol >= 0 && nextCol <= 2){
                    int nextNum = nextRow * 3 + nextCol + 1;
                    if(!visit[nextNum]){
                        break;
                    }
                    tempRow = nextRow;
                    tempCol = nextCol;
                }else {
                    hasNextPos = false;
                    break;
                }
            }
            // 回溯迭代
            if(hasNextPos){
                int nextNum = nextRow * 3 + nextCol + 1;
                visit[nextNum] = true;
                currentCount++;
                backtrace(currentCount, nextNum, visit, m, n);
                currentCount--;
                visit[nextNum] = false;
            }
        }
    }

二叉樹中和為某一值的路徑

• 正向思維，記錄當前路徑的和；注意作為參數(shù)的變量，在回溯調(diào)用之前和之后必須保持一致，所以在添加path到ans的時候，將當前節(jié)點的值加入的是剛new出來的rightAns中，而不是先加入path，再付給rightAns。

   public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();
        if(root == null){
            return ans;
        }
        dfs(ans, new ArrayList<>(), root, 0, sum);
        return ans;
    }

    public void dfs(List<List<Integer>> ans, List<Integer> path, TreeNode current, int pathSum, int sum){
        if(pathSum + current.val == sum && current.left == null && current.right == null){
            List<Integer> rightAns = new ArrayList<>(path);
            rightAns.add(current.val);
            ans.add(rightAns);
            return;
        }

        if(current.left != null){
            path.add(current.val);
            dfs(ans, path, current.left, pathSum + current.val, sum);
            path.remove(path.size()-1);
        }

        if(current.right != null){
            path.add(current.val);
            dfs(ans, path, current.right, pathSum + current.val, sum);
            path.remove(path.size()-1);
        }
    }

• 逆向思維，記錄剩下的路徑值。

    public void dfs(List<List<Integer>> ans, List<Integer> path, TreeNode current, int diff){
        if(current == null){
            return;
        }

        path.add(current.val);
        diff -= current.val;

        if(diff == 0 && current.left == null && current.right == null){
            ans.add(new ArrayList<>(path));
        }

        dfs(ans, path, current.left, diff);
        dfs(ans, path, current.right, diff);
        path.remove(path.size()-1);
    }

可能的二分法

• dislikes關(guān)系可以用鄰接矩陣表示；
• 數(shù)字分組的過程可以映射成給數(shù)字染色的過程，相鄰節(jié)點（數(shù)字）之間必須異色；
• 可以從1到N，逐一進行深度優(yōu)先染色，dfs函數(shù)表示：給某個數(shù)字染成某種顏色，是否能夠成功；如果從1到N都染色成功，則返回true；否則，返回false；
• dfs函數(shù)在給某個數(shù)字染色的時候，需要將鄰居染成異色；如果染色之前發(fā)現(xiàn)自己已經(jīng)是異色了，則矛盾，返回false；如果發(fā)現(xiàn)自己已經(jīng)是同色了，則已經(jīng)完成了染色，返回true；
• 技巧：可以使用數(shù)字1和-1表示異色，0表示未染色，這樣可以使用一個數(shù)組保存所有節(jié)點染色情況。

public boolean possibleBipartition(int N, int[][] dislikes) {
        List<Integer>[] table = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            table[i] = new ArrayList<>();
        }
        for (int i = 0; i < dislikes.length; i++) {
            int[] dis = dislikes[i];
            int num0 = dis[0];
            int num1 = dis[1];
            table[num0].add(num1);
            table[num1].add(num0);
        }
        int[] colored = new int[N+1]; // 0未染色, 1和-1代表相反的兩種顏色
        for(int number = 1; number <= N; number ++){
            if(colored[number] != 0){ // 已經(jīng)染過色, 下一個
                continue;
            }
            // 對number進行深度優(yōu)先染色: 注意既然前面所有的節(jié)點的深度優(yōu)先染色都沒有使number著色, 
            // 說明這個number與所有number都不是鄰居關(guān)系(即dislike關(guān)系)，所以這里隨便染成1或者-1都是正確的
            if(!dfs(number, 1, colored, table)){
                return false;
            }
        }
        return true;
    }

    // 深度優(yōu)先染色: color為-1/+1
    public boolean dfs(int number, int color, int[] colored, List<Integer>[] table) {
        if(colored[number] == -color){
            return false;
        }
        if(colored[number] == color){
            return true;
        }
        colored[number] = color; // 染色
        for(int neighbor : table[number]){
            if(!dfs(neighbor, -color, colored, table)){
                return false;
            }
        }
        return true;
    }

子集 II

• 同層去重

i > index && nums[i] == nums[i-1]

• 剪枝
• 按子集個數(shù)遍歷回溯函數(shù)

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for(int count = 0; count <= nums.length; count++){
            backtrace(ans, new ArrayList<>(), count, nums, 0);
        }
        return ans;
    }

    public void backtrace(List<List<Integer>> ans, List<Integer> sub, int count, int[] nums, int index){
        if(sub.size() == count){
            ans.add(new ArrayList<>(sub));
            return;
        }

        // 剪枝
        if(sub.size() + nums.length - index < count){
            return;
        }

        for(int i=index; i<nums.length; i++){
            // 同層去重
            if(i > index && nums[i] == nums[i-1]){
                continue;
            }
            sub.add(nums[i]);
            backtrace(ans, sub, count, nums, i+1);
            sub.remove(sub.size()-1);
        }
    }

字符串的排列

• 關(guān)鍵是如何通過剪枝去重：排序后去重：前后相鄰的元素如果相同，那么這些相同的連續(xù)元素中，只需要固定一次；一般選擇固定第一個元素，后面相同的元素不再固定。程序中判斷是否是第一個固定的元素，通過判斷前一個元素是否訪問過決定：如果前一個相同的元素已經(jīng)訪問過，說明是這些相同的元素都是第一次固定，否則就是第二次固定；

            if (i > 0 && chars[i] == chars[i - 1] && !visit[i - 1]) {
                continue;
            }

    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        List<String> ans = new ArrayList<>();
        backtrace(ans, new StringBuilder(), chars, new boolean[s.length()]);
        String[] ret = new String[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            ret[i] = ans.get(i);
        }
        return ret;
    }

    public void backtrace(List<String> ans, StringBuilder sb, char[] chars, boolean[] visit) {
        if (sb.length() == chars.length) {
            String s = new StringBuilder(sb).toString();
            ans.add(s);
            return;
        }

        for (int i = 0; i < chars.length; i++) {
            if (visit[i]) {
                continue;
            }
            // 去重(剪枝)
            if (i > 0 && chars[i] == chars[i - 1] && !visit[i - 1]) {
                continue;
            }
            sb.append(chars[i]);
            visit[i] = true;
            backtrace(ans, sb, chars, visit);
            visit[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }

• 另一種更加高效的寫法（算法的時間復雜度一樣），即另一種實現(xiàn)操作：是利用交換元素的操作，代替上面sb.append的操作。這種swap的操作在很多算法或技巧的實現(xiàn)中都用到了，所以建議必須掌握。
• 原理：想要得到某數(shù)組的一個全排列，一種做法是新建一個數(shù)組，然后從原數(shù)組中依次取元素到新數(shù)組空間中，待原數(shù)組的元素都取光了，新數(shù)組就是原數(shù)組的一個全排列，可以用visit數(shù)組記錄原數(shù)組哪些元素被取過，哪些元素沒有被取過。另一種做法是，不用新建一個數(shù)組，在原數(shù)組進行操作：依次固定第i個元素，固定的方法是從（i~length-1）元素中任取一個位置x上的元素放到第i個元素的位置上（即swap(i, x)），當固定到最后一個元素時，就得到原數(shù)組的一個全排列。
• 具體的過程為
  1）固定第0個元素，從(0~length-1)中選取位置x，然后交換元素swap(0, x)，即將位置x上的元素放置到位置0處；
  2）然后固定第1個元素，因為第0個元素已經(jīng)被固定了，所以第1個元素的候選者只能從(1~length-1)中選取位置x，然后交換元素swap(1, x)，即將位置x上的元素放置到1處；
  3）依次類推，當固定到第length-1個元素時，候選者只剩第length-1位置上的元素了，此刻得到原數(shù)組的全排列。
• 代碼如下，幾點說明
  1）backtrace方法的參數(shù)為pos，作用即為固定pos位置的數(shù)；
  2）這里去重的方法就比較容易理解多了：pos位置的數(shù)如果選取到了重復的數(shù)，則過濾；而且不再需要將原數(shù)組進行排序。

public class Solution {

    List<String> res = new LinkedList<>();
    char[] c;

    public String[] permutation(String s) {
        c = s.toCharArray();
        backtrace(0);
        return res.toArray(new String[res.size()]);
    }

    void backtrace(int pos) {
        if (pos == c.length - 1) {
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = pos; i < c.length; i++) {
            if (set.contains(c[i])) {
                continue; // 重復，因此剪枝
            }
            set.add(c[i]);
            swap(i, pos); // 交換，將 c[i] 固定在第 pos 位
            backtrace(pos + 1); // 開啟固定第 pos + 1 位字符
            swap(i, pos); // 恢復交換
        }
    }

    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }

}