LeetCode——全排列（DFS）

全排列是DFS的經典應用，無論是在平時的工作中還是在面試中，都是經常被問到的考點，接下來讓我們一起來探究這個問題吧。

題目描述

解題思路

本題的核心解題思路就是使用DFS(深度優先周遊),周遊完一條路徑然後再去周遊另一條路徑，通過使用一個used對象來記錄目标元素是否被周遊過，來實作DFS。

var permute = function(nums) {
    const result = [];
    const used = {};
    
    function dfs(paths) {
        if (paths.length === nums.length) {
            result.push(paths.slice());
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            paths.push(nums[i]);
            paths
            used[i] = true;
            dfs(paths);
            paths.pop();
            used[i] = false;
        }
    }
    
    dfs([])
    return result;
};
複制代碼      

題目反思

• DFS實作的核心在于使用一個對象來記錄目标元素是否周遊過。
• dfs周遊完一條路徑之後，需要将路徑數組中去掉棧頂元素，然後将該元素置未周遊狀态。