Matemáticas detrás del problema leetcode 47 permutaciones II
-
29-09-2020 - |
Pregunta
Por favor dime por qué la expresión i>0 && nums[i] == nums[i-1] && !used[i-1]
trabaja para obtener permutaciones únicas.¿Y cuál es la matemática detrás de esto?
El problema es el siguiente:
Dada una colección de números que pueden contener duplicados, devuelve todas las permutaciones únicas posibles.Ejemplo:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Aquí está el código:
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();
}
}
}
};
Solución
(1) Está ordenando el vector para que los valores duplicados estén presentes consecutivamente en el vector.
(2) Ahora llegamos a la lógica detrás de esa condición:
- Como el vector puede contener duplicados, debemos asegurarnos de no repetir la misma secuencia comenzando con el mismo elemento nuevamente (duplicar)
- ejemplo :
1,1,2
(empezando confirst
uno) y 1,1,2 (comenzando consecond
uno) => ambos son iguales (debemos asegurarnos de que esto no suceda)
- ejemplo :
Ejemplo:En [1, 1, 2]
Si el primer elemento de la secuencia se elige como 1, entonces debemos asegurarnos de no crear otra secuencia comenzando con otro 1 (duplicado del elemento).
Entonces, para eso, debemos omitir el ciclo de todos los elementos duplicados consecutivos.
En su caso, después de crear una secuencia comenzando con el primer 1, cuando ingresamos al bucle por segunda vez verificamos si el elemento actual es un duplicado.
nums[i] == nums[i - 1]
(esto es suficiente ya que ya ha ordenado el vector) y si el elemento actual es el primer elemento de la secuencia!used[i - 1]
.- En su caso, debido a esta condición, el segundo no puede ser el primer elemento de la secuencia.