C++의 순열 II

고유한 정수 모음이 있다고 가정합니다. 가능한 모든 순열을 찾아야 합니다. 이제 배열에 중복 요소가 저장되어 있으면 비슷하게 보이는 상태를 무시하십시오. 따라서 배열이 [1,1,3]과 같으면 결과는 [[1,1,3], [1,3,1], [3,1,1]]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 재귀적 접근 방식을 사용하여 목록, 색인을 만듭니다. 색인은 처음에 0입니다.
• 인덱스 =목록의 크기인 경우 res 배열에 목록을 삽입하고 반환
• 주어진 목록의 길이에 대한 범위 인덱스의 i에 대해 – 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]]