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>
