중복 결과가없는 배열의 모든 순열 생성

Question

이것은 permutation2 리셋 코드 질문입니다.

배열 num (요소가 1,1,2와 같이 고유하지 않음)이 주어진다면 중복 결과없이 모든 순열을 반환하십시오. 예를 들어, num = {1,1,2}은 {1,1,2},{1,2,1},{2,1,1}의 순열을 가져야합니다.

나는 다음과 같은 해결책을 제시했다. 기본적으로, 나는 반복적으로 순열을 생성한다. [0, begin-1]이 고정되어 있다고 가정하면, 재귀 적으로 [begin, lastElement]의 순열을 생성합니다. 내 엑스 코드 IDE 여러 경우에 정답을 반환 할 수 있습니다 동안 leetcode의 OJ가 나에게 출력 제한을 준 이후이 적합한 솔루션이 경우

vector<vector<int> > permuteUnique(vector<int> &num) { 
    vector<vector<int> > res; 
    if(num.empty()) 
     return res; 
    helper(num, 0, res); 
    return res; 
} 
//0...begin-1 is already permutated 
void helper(vector<int> &num, int begin, vector<vector<int> > &res) 
{ 
    if(begin == num.size()) 
    { 
     res.push_back(num);//This is a permutation 
     return; 
    } 
    for(int i = begin; i<num.size(); ++i) 
    { 
     if(i!=begin&&num[i]==num[begin])//if equal, then [begin+1,lastElement] would have same permutation, so skip 
      continue; 
     swap(num[i], num[begin]); 
     helper(num, begin+1, res); 
     swap(num[i], num[begin]); 
    } 
} 

궁금 해서요.

내 관심사는 if(i!=begin&&num[i]==num[begin])continue;이 실제로 중복 결과를 건너 뛸 수 있습니까? 그렇지 않다면, 반례문은 무엇입니까?

의견을 보내 주셔서 감사합니다.

Answer 1

STL과 함께, 코드가 될 수있다 :

std::vector<std::vector<int> > permuteUnique(std::vector<int> num) { 
    std::sort(num.begin(), num.end()); 
    std::vector<std::vector<int> > res; 
    if(num.empty()) { 
     return res; 
    } 
    do { 
     res.push_back(num); 
    } while (std::next_permutation(num.begin(), num.end())); 
    return res; 
} 

Live demo

귀하의 테스트 중복을 건너 충분하지 않습니다. 등록 {2, 1, 1}의 경우 :

{2, 1, 1} 
{1, 2, 1} 
{1, 1, 2} 
{1, 1, 2} 
{1, 2, 1} 

그래서 2 개의 사본이 있습니다.