[Leedcode][JAVA][第46題][全排列][回溯算法]

【問題描述】 46.全排列 （中等）

給定一個 沒有重複 數字的序列，傳回其所有可能的全排列。

示例:

輸入: [1,2,3]
輸出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]


           

【解答思路】

1. 回溯

時間複雜度：O(NN！) 空間複雜度：O(NN！)

public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        // 首先是特判
        int len = nums.length;
        // 使用一個動态數組儲存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();

        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
//不能直接path 
//path 這個變量所指向的對象在遞歸的過程中隻有一份，深度優先周遊完成以後，因為回到了根結點（因為我們之前說了，從深層結點回到淺層結點的時候，需要撤銷之前的選擇），是以 path 這個變量回到根結點以後都為空。
            res.add(new ArrayList<>(path));
            return;
        }
//contains時間複雜度更高
 //if (path.contains(nums[i])) {
//                continue;
//            }
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;

                dfs(nums, len, depth + 1, path, used, res);
                // 注意：這裡是狀态重置，是從深層結點回到淺層結點的過程，代碼在形式上和遞歸之前是對稱的
                used[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution solution = new Solution();
        List<List<Integer>> lists = solution.permute(nums);
        System.out.println(lists);
    }
}

作者：liweiwei1419
連結：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

           

建立新的變量 不回溯

import java.util.ArrayList;
import java.util.List;


public class Solution {

    public List<List<Integer>> permute(int[] nums) {
        // 首先是特判
        int len = nums.length;
        // 使用一個動态數組儲存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();

        if (len == 0) {
            return res;
        }

        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();

        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth,
                     List<Integer> path, boolean[] used,
                     List<List<Integer>> res) {
        if (depth == len) {
            // 3、不用拷貝，因為每一層傳遞下來的 path 變量都是建立的
            res.add(path);
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                // 1、每一次嘗試都建立新的變量表示目前的"狀态"
                List<Integer> newPath = new ArrayList<>(path);
                newPath.add(nums[i]);

                boolean[] newUsed = new boolean[len];
                System.arraycopy(used, 0, newUsed, 0, len);
                newUsed[i] = true;

                dfs(nums, len, depth + 1, newPath, newUsed, res);
                // 2、無需回溯
            }
        }
    }
}


           

另一種寫法

List<List<Integer>> res = new LinkedList<>();

/* 主函數，輸入一組不重複的數字，傳回它們的全排列 */
List<List<Integer>> permute(int[] nums) {
    // 記錄「路徑」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

// 路徑：記錄在 track 中
// 選擇清單：nums 中不存在于 track 的那些元素
// 結束條件：nums 中的元素全都在 track 中出現
void backtrack(int[] nums, LinkedList<Integer> track) {
    // 觸發結束條件
    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();
    }
}

作者：labuladong
連結：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-xiang-jie-by-labuladong-2/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
           

【總結】

1.回溯算法總結

「回溯算法」是在一個「樹形問題」上的「深度優先周遊」，是「深度優先周遊」在搜尋問題上的另一種叫法。

• 調隻使用一份「狀态」變量去搜尋整個狀态空間，在狀态空間很大的時候，這種做法是節約空間的，并且在一定程度上也是節約時間的。

  -在不滿足條件的時候（或者是找到了一個解以後），會回到之前的結點，以搜尋更多的解，是以有「回溯」的需求。

2.為什麼使用深度優先周遊？

（1）首先是正确性，隻有周遊狀态空間，才能得到所有符合條件的解；

（2）在深度優先周遊的時候，不同狀态之間的切換很容易，可以再看一下上面有很多箭頭的那張圖，每兩個狀态之間的差别隻有 1 處，是以回退非常友善，這樣全局才能使用一份狀态變量完成搜尋；

（3）如果使用廣度優先周遊，從淺層轉到深層，狀态的變化就很大，此時我們不得不在每一個狀态都建立變量去儲存它，從性能來說是不劃算的；

（4）如果使用廣度優先周遊就得使用隊列，然後編寫結點類。使用深度優先周遊，我們是直接使用了系統棧，系統棧幫助我們儲存了每一個結點的狀态資訊。于是我們不用編寫結點類，不必手動編寫棧完成深度優先周遊。

3.回溯算法tips

• 回溯算法會大量應用“剪枝”技巧達到以加快搜尋速度。有些時候，需要做一些預處理工作（例如排序）才能達到剪枝的目的。
• 預處理工作雖然也消耗時間，但一般而且能夠剪枝節約的時間更多。還有正是因為回溯問題本身時間複雜度就很高，是以能用空間換時間就盡量使用空間。否則時間消耗又上去了。
• 先畫圖，畫圖是非常重要的，隻有畫圖才能幫助我們想清楚遞歸結構，想清楚如何剪枝。

  

4.對代碼的思考

5.回溯法模闆

if 滿足結束條件:
        result.add(路徑)
        return
for 選擇 in 選擇清單:
    #排除不合法的選擇d
    将該選擇從選擇清單移除（used數組 /條件限制）
    # 做選擇
    路徑.add(選擇)
    backtrack(路徑, 選擇清單)
    # 撤銷選擇
    路徑.remove(選擇)
  

           

作者連結：https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/