Написано: 14.03.2023
47. Перестановки II (Permutations II)
Задание.
Получен массив 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]]
Решение.
class Solution {
private:
vector<vector<int>> result;
set<vector<int>> ans;
void permute(vector<int>& nums, int start) {
int len = (int)nums.size();
if (start == len - 1) {
ans.insert(nums);
} else {
for (int i = start; i < len; i++) {
if(i > start) { swap(nums[start], nums[i]); }
permute(nums, start + 1);
if(i > start) { swap(nums[start], nums[i]); }
}
}
return;
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
permute(nums, 0);
for(auto it: ans) result.push_back(it);
return result;
}
};