Giả sử chúng ta có một tập hợp các số nguyên riêng biệt; chúng ta phải tìm tất cả các hoán vị có thể có. Bây giờ nếu mảng lưu trữ các phần tử trùng lặp, thì hãy bỏ qua trạng thái trông giống nhau đó. Vì vậy, nếu mảng giống như [1,1,3], thì kết quả sẽ là [[1,1,3], [1,3,1], [3,1,1]]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Chúng tôi sẽ sử dụng phương pháp đệ quy, điều này sẽ tạo danh sách, lập chỉ mục. Chỉ mục ban đầu là 0
- nếu chỉ mục =kích thước của danh sách, sau đó chèn danh sách vào mảng res và trả về
- cho tôi trong chỉ mục phạm vi đến độ dài của danh sách đã cho - 1
- nếu list [i] =list [index] và tôi không giống với index, thì hãy tiếp tục mà không cần xem bước tiếp theo
- hoán đổi các phần tử của danh sách hiện tại khi bắt đầu chỉ mục và tôi
- hoán vị (danh sách, bắt đầu + 1)
- ban đầu gọi hoán vị (danh sách) và trả về res
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
[1,1,3]
Đầu ra
[[1,1,3],[1,3,1],[3,1,1]]