Permutations

Permutations.png

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

同樣使用 backtrack 的方式不斷放入 element 進入一組 tmp vector, 每放入一筆資料就馬上 recursive 的做 DFS 檢查. 當 tmp 放滿跟題目給的 vector 等量的資料時 相當於找到一組排列方式 即可存入 result 之中. 在 for loop 進行檢索的時候 重點只能放入當前 tmp vector 還尚未放入過的資料 所以有一個 find 的步驟塞選能放入的資料

===================== C++ code ====================

<pre><code>
class Solution {

public:

 /**
 * @param nums: A list of integers.
 * @return: A list of permutations.
 */
void BT(vector<vector<int>> &res, vector<int> &tmp, vector<int> nums)
{
    if(tmp.size() == nums.size()) res.emplace_back(tmp);
    else{
        for(int i = 0; i < nums.size(); i++)
        {
            if(find(tmp.begin(), tmp.end(), nums[i]) == tmp.end())
            {
                tmp.emplace_back(nums[i]);
                BT(res, tmp, nums);
                tmp.pop_back();
            }
        }
    }
}
 
vector<vector<int> > permute(vector<int> nums) {
    // write your code here
   vector<vector<int>> res;
   vector<int> tmp;
   sort(nums.begin(), nums.end());
   BT(res, tmp, nums);
   return res;
}

};
<code><pre>