Permutations II

Permutations II.png

===================== 解題思路 =====================

類似 Permutations 的做法 但是另外建立一個 boolean vector 紀錄當前的 nums 使用情形以下兩種情況將跳過目前 loop 過程中的資料

1. 已經使用過的位置（nums 中的位置), 即 used[i] = true
2. 尚未使用過 但是當前數字跟前一個數字相同 而前一個數字尚未使用過

避開這兩種情況 其他都跟 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>