Permutations II.png
===================== 解題思路 =====================
類似 Permutations 的做法 但是另外建立一個 boolean vector 紀錄當前的 nums 使用情形以下兩種情況將跳過目前 loop 過程中的資料
- 已經使用過的位置（nums 中的位置), 即 used[i] = true
- 尚未使用過 但是當前數字跟前一個數字相同 而前一個數字尚未使用過
避開這兩種情況 其他都跟 DFS 的基本做法相同 在放入資料的同時設定 used 為 true, 然後進行 recursive call, 接著 pop 這筆資料的同時回覆 used 為 false, 另外再次提醒我每次都會忘記的事, 切記先 sort 過來源給的 nums !!!!
===================== C++ code ====================
<pre><code>
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: A list of unique permutations.
*/
void BT(vector<vector<int>> &res, vector<int> &tmp, vector<int> &nums, vector<bool> &used)
{
if(tmp.size() == nums.size()) res.emplace_back(tmp);
else{
for(int i = 0; i < nums.size(); i++)
{
if(used[i]) continue;
if(i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
used[i] = true;
tmp.emplace_back(nums[i]);
BT(res, tmp, nums, used);
tmp.pop_back();
used[i] = false;
}
}
}
vector<vector<int> > permuteUnique(vector<int> &nums) {
// write your code here
vector<vector<int>> res;
vector<int> tmp;
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
BT(res, tmp, nums, used);
return res;
}
};
<code><pre>
