AskOverflow.Dev

AskOverflow.Dev Logo AskOverflow.Dev Logo

AskOverflow.Dev Navigation

  • Início
  • system&network
  • Ubuntu
  • Unix
  • DBA
  • Computer
  • Coding
  • LangChain

Mobile menu

Close
  • Início
  • system&network
    • Recentes
    • Highest score
    • tags
  • Ubuntu
    • Recentes
    • Highest score
    • tags
  • Unix
    • Recentes
    • tags
  • DBA
    • Recentes
    • tags
  • Computer
    • Recentes
    • tags
  • Coding
    • Recentes
    • tags
Início / coding / Perguntas / 79561035
Accepted
ContravariantMind
ContravariantMind
Asked: 2025-04-08 09:59:22 +0800 CST2025-04-08 09:59:22 +0800 CST 2025-04-08 09:59:22 +0800 CST

Confusão de retrocesso

  • 772

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.

javascript
  • 1 1 respostas
  • 49 Views

1 respostas

  • Voted
  1. Best Answer
    Nick Parsons
    2025-04-08T10:49:15+08:002025-04-08T10:49:15+08:00

    Passamos por i=0 novamente, mas temp já tem o valor 1, então continuamos

    Não exatamente. Depois pop()de lidar com [1, 2], você não olha i = 0para essa permutação novamente. Depois de terminar de olhar para [1, 2], sua backtrackchamada anterior estava olhando para i=1, e então quando você pop(), seu loop completa suas iterações, e você volta para a backtrackchamada anterior que adicionou [1](que tem um i=0). Isso então chama pop()novamente, definindo tempde volta para um array vazio, onde seu loop então itera para i=1onde você envia 2, a chamada de backtrack então envia 1para 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):

    backtrack([])
    ├─ i=0 -> push 1 -> temp = [1]
    │  └─ backtrack([1])
    │     ├─ i=0 -> skip (1 in temp)
    │     ├─ i=1 -> push 2 -> temp = [1,2]
    │     │  └─ backtrack([1,2]) -> add [1,2] to `result`
    │     └─ pop -> temp = [1] (note: here, i=1, so loop finishes)
    └─ pop -> temp = []
    
    ├─ i=1 -> push 2 -> temp = [2]
    │  └─ backtrack([2])
    │     ├─ i=0 -> push 1 -> temp = [2,1]
    │     │  └─ backtrack([2,1]) -> add [2,1] to `result`
    │     ├─ pop -> temp = [2]
    │     └─ i=1 -> skip (2 in temp) [note: after this, the loop finishes)
    └─ pop -> temp = []
    
    • 2

relate perguntas

  • classificação de mesclagem não está funcionando - código Javascript: não é possível encontrar o erro mesmo após a depuração

  • método select.remove() funciona estranho [fechado]

  • Sempre um 401 res em useOpenWeather () - react-open-weather lib [duplicado]

  • O elemento de entrada não possui atributo somente leitura, mas os campos ainda não podem ser editados [fechado]

  • Como editar o raio do primeiro nó de um RadialTree D3.js?

Sidebar

Stats

  • Perguntas 205573
  • respostas 270741
  • best respostas 135370
  • utilizador 68524
  • Highest score
  • respostas
  • Marko Smith

    Reformatar números, inserindo separadores em posições fixas

    • 6 respostas
  • Marko Smith

    Por que os conceitos do C++20 causam erros de restrição cíclica, enquanto o SFINAE antigo não?

    • 2 respostas
  • Marko Smith

    Problema com extensão desinstalada automaticamente do VScode (tema Material)

    • 2 respostas
  • Marko Smith

    Vue 3: Erro na criação "Identificador esperado, mas encontrado 'import'" [duplicado]

    • 1 respostas
  • Marko Smith

    Qual é o propósito de `enum class` com um tipo subjacente especificado, mas sem enumeradores?

    • 1 respostas
  • Marko Smith

    Como faço para corrigir um erro MODULE_NOT_FOUND para um módulo que não importei manualmente?

    • 6 respostas
  • Marko Smith

    `(expression, lvalue) = rvalue` é uma atribuição válida em C ou C++? Por que alguns compiladores aceitam/rejeitam isso?

    • 3 respostas
  • Marko Smith

    Um programa vazio que não faz nada em C++ precisa de um heap de 204 KB, mas não em C

    • 1 respostas
  • Marko Smith

    PowerBI atualmente quebrado com BigQuery: problema de driver Simba com atualização do Windows

    • 2 respostas
  • Marko Smith

    AdMob: MobileAds.initialize() - "java.lang.Integer não pode ser convertido em java.lang.String" para alguns dispositivos

    • 1 respostas
  • Martin Hope
    Fantastic Mr Fox Somente o tipo copiável não é aceito na implementação std::vector do MSVC 2025-04-23 06:40:49 +0800 CST
  • Martin Hope
    Howard Hinnant Encontre o próximo dia da semana usando o cronógrafo 2025-04-21 08:30:25 +0800 CST
  • Martin Hope
    Fedor O inicializador de membro do construtor pode incluir a inicialização de outro membro? 2025-04-15 01:01:44 +0800 CST
  • Martin Hope
    Petr Filipský Por que os conceitos do C++20 causam erros de restrição cíclica, enquanto o SFINAE antigo não? 2025-03-23 21:39:40 +0800 CST
  • Martin Hope
    Catskul O C++20 mudou para permitir a conversão de `type(&)[N]` de matriz de limites conhecidos para `type(&)[]` de matriz de limites desconhecidos? 2025-03-04 06:57:53 +0800 CST
  • Martin Hope
    Stefan Pochmann Como/por que {2,3,10} e {x,3,10} com x=2 são ordenados de forma diferente? 2025-01-13 23:24:07 +0800 CST
  • Martin Hope
    Chad Feller O ponto e vírgula agora é opcional em condicionais bash com [[ .. ]] na versão 5.2? 2024-10-21 05:50:33 +0800 CST
  • Martin Hope
    Wrench Por que um traço duplo (--) faz com que esta cláusula MariaDB seja avaliada como verdadeira? 2024-05-05 13:37:20 +0800 CST
  • Martin Hope
    Waket Zheng Por que `dict(id=1, **{'id': 2})` às vezes gera `KeyError: 'id'` em vez de um TypeError? 2024-05-04 14:19:19 +0800 CST
  • Martin Hope
    user924 AdMob: MobileAds.initialize() - "java.lang.Integer não pode ser convertido em java.lang.String" para alguns dispositivos 2024-03-20 03:12:31 +0800 CST

Hot tag

python javascript c++ c# java typescript sql reactjs html

Explore

  • Início
  • Perguntas
    • Recentes
    • Highest score
  • tag
  • help

Footer

AskOverflow.Dev

About Us

  • About Us
  • Contact Us

Legal Stuff

  • Privacy Policy

Language

  • Pt
  • Server
  • Unix

© 2023 AskOverflow.DEV All Rights Reserve