【LeetCode】全排列 - 回溯演算法 - JavaScript描述

語言: CN / TW / HK

theme: cyanosis highlight: a11y-dark


小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動。

本文已參與「掘力星計劃」,贏取創作大禮包,挑戰創作激勵金。

高中在學習排列組合的時候就學過全排列了,今天我們用程式來實現全排列。也就是說我們要將人類進行全排列的行為方式抽象成自動化的程式語言。這題我在 [快手一面] 中遇到過

這種全排列就是遍歷出每一種可能,我們採用回溯演算法來進行操作,其實這就是一個決策樹的遍歷過程

46. 全排列

給定一個不含重複數字的陣列 nums ,返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

我們先舉一個例子假設要進行1,2,3的全排列

我們首先在1,2,3中任選一個,假設是1,然後在剩下的2,3中任選一個,假設是2,最後剩下3,就選它就行了。我們畫一棵【1,2,3】排列的決策樹看看

我們來抽象一下,首先定義一個路徑列表表示我們選擇過的元素,然後定義一個選擇列表,來表示我們還可以選擇的元素,最後當到達葉子結點的時候,就表示遍歷結束,返回當前的路徑列表即可

image.png

圖中 [1,2,3] 這種表示的是選擇列表,綠色的數字表示的是每次的決策,葉子節點上的序列就是一個排列

我們要遍歷出所有的排列結果,所以我們到達葉子結點拿到一個序列之後需要回溯,回溯就要放出自己剛剛決策的那個元素,放回選擇列表中去。

這裡的選擇列表,我們定義為一個標記陣列used,用來標記每一個節點是否已經被選擇,這樣沒有被選擇的元素構成了選擇列表

再具體的內容,看我程式碼中的註釋,寫的很是詳細了~

【解法】回溯

```javascript /* * @param {number[]} nums * @return {number[][]} / var permute = function (nums) { // 儲存結果陣列,儲存每個路徑(排列) const result = []; // 呼叫回溯函式,傳入引數 backtracking(nums, nums.length, [], []); // 返回結果陣列 return result;

// 定義回溯遞迴函式,傳入陣列,長度,節點是否被使用過的陣列 // used 用來標記節點是否被用過 path 用來儲存路徑,定義為一個棧 function backtracking(nums, len, used, path) { // 遞迴出口 // 如果到達葉子節點,將路徑推入結果陣列,並返回 if (path.length === len) { result.push([...path]); return; } // 遍歷候選字元 for (let i = 0; i < len; i++) { // 使用過就下一輪迴圈 if (!used[i]) { // undefind和fasle都會進來 // 這裡說明這個數還沒有被使用,入棧path path.push(nums[i]); // 標記這個數被使用過了 used[i] = true; // 開始進行遞迴 backtracking(nums, len, used, path); // 回溯【狀態重置】撤銷之前的操作 path.pop(); used[i] = false; } } } }; ```

最後我們看一下結果

在這裡插入圖片描述

「其他文章」