Giả sử chúng ta có một tập hợp các số nguyên khác nhau; ta phải tìm tất cả các hoán vị có thể. Nếu mảng chứa phần tử trùng lặp, bỏ qua trạng thái trùng lặp. Ví dụ, mảng [1,1,3], kết quả [[1,1,3], [1,3,1], [3,1,1]].
Để giải quyết, ta làm theo các bước:
- Dùng đệ quy, hàm nhận danh sách, index (khởi tạo 0)
- nếu index = kích thước danh sách, thêm danh sách vào res, return
- for i từ index đến độ dài danh sách – 1
- nếu list[i] = list[index] và i khác index, continue
- hoán đổi phần tử tại index và i
- permutation(list, start + 1)
- gọi permutation(list) ban đầu, return res
Ví dụ (C++)
Hãy xem triển khai sau:
#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)); }Input
[1,1,3]
Output
[[1,1,3],[1,3,1],[3,1,1]]