O backtracking explora escolhas mantendo estado suficiente para rejeitar respostas parciais impossíveis. Um ramo pode escolher um pacote, posicionar uma câmera ou entrar na próxima célula da rota de uma palavra. Antes da recursão, aplique a escolha. Quando o ramo voltar, restaure todas as partes do estado que a escolha alterou. Uma restauração que falta pode fazer ramos sem relação herdarem as restrições uns dos outros.
Valores repetidos na entrada exigem interpretação cuidadosa. Pacotes de mesmo peso continuam distintos quando as seleções se referem a índices de pacotes. Letras de crachá repetidas são indistinguíveis quando você retorna strings únicas. São contratos de contagem diferentes. Ordenar ajuda a podar escolhas equivalentes, mas só quando a tarefa as trata como equivalentes. Comece com uma árvore de seleção binária e depois trate as saídas duplicadas, a capacidade restante e as restrições do tabuleiro. A última tarefa combina vários conjuntos de conflitos simultâneos.
Escolher um dos pacotes iguais pode produzir um subconjunto de índices diferente.