Em relação ao Javascript, tenho tentado entender o backtracking ultimamente e está bem confuso. Especificamente, tenho tentado entender o problema da permutação, em que, quando dado um array, queremos todas as permutações possíveis desse array:
function permute(nums) {
let result = [];
function backtrack(temp = []) {
if (temp.length === nums.length) {
result.push([...temp]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (temp.includes(nums[i])) continue;
temp.push(nums[i]);
backtrack(temp);
temp.pop();
}
}
backtrack();
return result;
}
Vamos considerar nums = [1,2] para simplificar. \
Pelo que entendi, começamos em temp=[], em i=0 temp -> [1], e o backtrack deve procurar os outros valores possíveis (apenas 2). Ele ignora a exclusão do suposto valor em temp.pop() e retorna ao loop onde i=1 agora e temp [1] -> [1,2] e, agora que satisfaz a condição de comprimento, uma cópia deste array temporário é anexada ao array resultante. Então, minha pergunta é: o que acontece após essa adição?
Supostamente, o código fornecido acima retorna [[1,2],[2,1]], o que está correto, mas não entendo o porquê. Após a adição, aparentemente extraímos o valor final de temp, agora em [1], e reiniciamos o loop em i, já que o terminamos para obter [1,2]. Passamos por i=0 novamente, mas temp já tem o valor 1, então continuamos. Então, ele recebe 2 novamente, e o backtrack envia este resultado para verificar a condição inicial de comprimento, não é? Aparentemente, ele deve extrair duas vezes e iniciar o loop em i=1 para que o backtrack tenha backtrack([2]) e, em seguida, procurar o 1 ausente.
Não entendo onde está minha falha, mas sei que há algum erro de interpretação em algum lugar, só não entendo onde.
Não exatamente. Depois
pop()
de lidar com[1, 2]
, você não olhai = 0
para essa permutação novamente. Depois de terminar de olhar para[1, 2]
, suabacktrack
chamada anterior estava olhando parai=1
, e então quando vocêpop()
, seu loop completa suas iterações, e você volta para abacktrack
chamada anterior que adicionou[1]
(que tem umi=0
). Isso então chamapop()
novamente, definindotemp
de volta para um array vazio, onde seu loop então itera parai=1
onde você envia2
, a chamada de backtrack então envia1
para você[2, 1]
, que é adicionado ao seu resultado na chamada de backtrack subsequente. Aqui está uma visualização em árvore das chamadas de backtrack aninhadas em ação que pode ajudar (veja a primeira nota, que é onde seu mal-entendido parece estar):