Leetcode 문제 47 순열 II의 수학

Question

표현이 왜 나오는지 알려주세요 i>0 && nums[i] == nums[i-1] && !used[i-1] 고유한 순열을 얻는 데 작동합니다.그리고 그 뒤에 숨겨진 수학은 무엇입니까?
문제는 다음과 같습니다.
중복된 숫자가 포함될 수 있는 숫자 모음이 있는 경우 가능한 모든 고유 순열을 반환합니다.예:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

코드는 다음과 같습니다.

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {   
        vector<vector<int>> result; 
        vector<int> temp;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtrack(nums, temp, result, used);
        return result;        
    }
    
    void backtrack(vector<int>& nums, vector<int>& temp, vector<vector<int>>& result, vector<bool>& used){
        
        if(temp.size() == nums.size()){
            result.emplace_back(temp);
        }else{
            
            for(int i=0; i<nums.size(); i++){
                if(used[i] || i>0 && nums[i] == nums[i-1] && !used[i-1]) continue; 
                used[i] = true;
                temp.push_back(nums[i]);
                backtrack(nums, temp, result, used);
                used[i] = false;
                temp.pop_back();
            }            
        }        
    }    
};

Answer 1

(1) 중복 값이 ​​벡터에 연속적으로 존재하도록 벡터를 정렬합니다.

(2) 이제 우리는 그 조건 뒤에 있는 논리에 이르렀습니다.

• 벡터에는 중복 항목이 포함될 수 있으므로 동일한 요소로 다시 시작하여 동일한 시퀀스를 반복하지 않도록 해야 합니다(중복).
  • 예 :
    • 1,1,2 (로 시작 first 1) 및 1,1,2(다음으로 시작) second one) => 둘 다 동일합니다(이런 일이 발생하지 않도록 해야 합니다).

예:~ 안에 [1, 1, 2]

• 시퀀스의 첫 번째 요소가 1로 선택되면 다른 1(요소의 중복)로 시작하는 다른 시퀀스를 생성하지 않도록 해야 합니다.

• 따라서 이를 위해서는 모든 연속된 중복 요소에 대해 루프를 건너뛰어야 합니다.

• 귀하의 경우 처음 1부터 시작하는 시퀀스를 만든 후 두 번째로 루프에 들어갈 때 현재 요소가 중복되는지 확인합니다. nums[i] == nums[i - 1] (이미 벡터를 정렬했으므로 이것으로 충분합니다.) 현재 요소가 시퀀스의 첫 번째 요소인지 여부 !used[i - 1].

  • 귀하의 경우 이 조건으로 인해 두 번째 요소가 시퀀스의 첫 번째 요소가 될 수 없습니다.