สมมติว่าเรามีคอลเล็กชันของจำนวนเต็มที่แตกต่างกัน เราต้องหาการเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมด ตอนนี้ ถ้าอาร์เรย์เก็บองค์ประกอบที่ซ้ำกัน ให้ละเว้นสถานะที่มีลักษณะคล้ายกัน ดังนั้นหากอาร์เรย์เป็นแบบ [1,1,3] ผลลัพธ์จะเป็น [1,1,3], [1,3,1], [3,1,1]]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เราจะใช้วิธีเรียกซ้ำ ซึ่งจะทำให้รายการ ดัชนี ดัชนีเริ่มต้น 0
- ถ้าดัชนี =ขนาดของรายการ ให้แทรกรายการลงในอาร์เรย์ res และส่งคืน
- สำหรับฉันอยู่ในช่วงดัชนีถึงความยาวของรายการที่กำหนด – 1
- ถ้า list[i] =list[index] และ i ไม่เหมือนกับ index ให้ดำเนินการต่อโดยไม่ดูขั้นตอนต่อไป
- สลับองค์ประกอบของรายการที่แสดงเมื่อเริ่มต้นดัชนีและ i
- การเปลี่ยนแปลง (รายการ เริ่ม + 1)
- ในขั้นแรกเรียกการเปลี่ยนแปลง (รายการ) และส่งคืน res
ตัวอย่าง(C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
void solve(vector <int> nums, int idx = 0){
if(idx == nums.size()){
res.push_back(nums);
return;
}
for(int i = idx; i <nums.size(); i++){
if(nums[i] == nums[idx] && i != idx)continue;
swap(nums[i], nums[idx]);
solve(nums, idx + 1);
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
res.clear();
sort(nums.begin(), nums.end());
solve(nums);
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,1,3};
print_vector(ob.permuteUnique(v));
} อินพุต
[1,1,3]
ผลลัพธ์
[[1,1,3],[1,3,1],[3,1,1]]
