1、題目描述：

給定一個可包含重復數字的序列?nums?，按任意順序?返回所有不重復的全排列。

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

---

2、代碼:

#include <algorithm>
#include <vector>
using namespace std;class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end()); // 排序使相同元素相鄰，方便后續剪枝vector<vector<int>> result;      // 存儲所有唯一排列的結果集vector<int> path;               // 當前遞歸路徑的排列vector<bool> used(nums.size(), false); // 標記元素是否被使用過backtrack(nums, result, path, used);return result;}private:void backtrack(vector<int>& nums, vector<vector<int>>& result,vector<int>& path, vector<bool>& used) {// 終止條件：當前路徑長度等于數組長度，得到一個完整排列if (path.size() == nums.size()) {result.push_back(path);return;}// 遍歷所有元素選擇可能的排列元素for (int i = 0; i < nums.size(); i++) {// 剪枝條件（核心邏輯）：// 1. 當前元素已被使用過，跳過// 2. 當前元素與前一個元素相同，且前一個元素未被使用（樹層剪枝）if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {continue;}// 選擇當前元素used[i] = true;           // 標記為已使用path.push_back(nums[i]);  // 加入當前路徑backtrack(nums, result, path, used); // 遞歸進入下一層選擇// 回溯操作（狀態重置）path.pop_back();          // 從路徑移除最后添加的元素used[i] = false;          // 恢復元素未使用狀態}}
};

---

3、解題思路:

1. ??排序預處理??

   • 先對數組排序，使相同元素相鄰，便于后續剪枝判斷重復元素。
   • 示例：[1,1,2]?→ 排序后為?[1,1,2]。

2. ??回溯框架??

   • 通過遞歸遍歷所有可能的排列組合。
   • path?記錄當前路徑，used?標記已使用的元素，result?存儲結果。

3. ??剪枝策略??

   • ??跳過已使用元素??：若?used[i] == true，直接跳過。
   • ??樹層剪枝??：若當前元素與前一個相同，且前一個未被使用，跳過當前元素。
     （避免同一層遞歸中選擇相同元素，消除重復排列，前一個相同元素未被使用，說明在更淺的遞歸層已經被處理過，當前層需要跳過以避免重復）