💢歡迎來到張胤塵的技術站
💥技術如江河，匯聚眾志成。代碼似星辰，照亮行征程。開源精神長，傳承永不忘。攜手共前行，未來更輝煌💥

官方站點： 力扣 Leetcode

算法每日一練 (11)

全排列

題目地址：全排列

題目描述

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

示例 1：

輸入：nums = [1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums = [0,1]
輸出：[[0,1],[1,0]]

示例 3：

輸入：nums = [1]
輸出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整數 互不相同

解題思路

• 整體解題流程采用回溯的思路。
• 首先遞歸終止條件，如果當前狀態已經滿足了子集的條件，則返回到上一層。在本題中，遞歸終止條件就是當前索引到達了數組末尾，則無需向下繼續遞歸。
• 緊接著就是在遞歸的過程中，枚舉所有可能的選擇，并針對每種情況都進行處理。
• 從當前索引開始，嘗試交換每個位置的元素，然后遞歸的調用 backtrack 方法處理每一種情況。
• 緊接著回溯是關鍵步驟，在每次遞歸返回后，需要撤銷當前的選擇，恢復到上一步的狀態，以便嘗試其他可能性。
• 最后當所有的排列全部列舉完畢后，返回 result 結果集即可。

解題代碼

c/c++

#include <vector>class Solution
{
public:std::vector<std::vector<int>> permute(std::vector<int> &nums){std::vector<std::vector<int>> result;std::vector<int> current = nums;backtrack(result, current, 0);return result;}private:void backtrack(std::vector<std::vector<int>> &result, std::vector<int> &current, int start){if (start == current.size()){result.push_back(current);return;}for (int i = start; i < current.size(); ++i){std::swap(current[start], current[i]);backtrack(result, current, start + 1);std::swap(current[start], current[i]);}}
};

golang

func permute(nums []int) [][]int {result := [][]int{}backtrack(&result, &nums, 0)return result
}func backtrack(result *[][]int, current *[]int, start int) {sz := len(*current)if start == sz {perm := make([]int, sz)copy(perm, *current)*result = append(*result, perm)return}for i := start; i < sz; i++ {(*current)[i], (*current)[start] = (*current)[start], (*current)[i]backtrack(result, current, start+1)(*current)[i], (*current)[start] = (*current)[start], (*current)[i]}return
}

lua

local function copyTable(t)local copy = {}for i = 1, #t docopy[i] = t[i]endreturn copy
endlocal function backtrack(result, current, start)local sz = #currentif sz == start thentable.insert(result, copyTable(current))returnendfor i = start, sz docurrent[i], current[start] = current[start], current[i]backtrack(result, current, start + 1)current[i], current[start] = current[start], current[i]end
endlocal function permute(nums)local result = {}backtrack(result, nums, 1)return result
end

🌺🌺🌺撒花！

如果本文對你有幫助，就點關注或者留個👍
如果您有任何技術問題或者需要更多其他的內容，請隨時向我提問。