Blog 2: padrão de conjunto de subconjuntos e energia

O retorno é especialmente poderoso para problemas, onde precisamos explorar todos os subconjuntos ou combinações possíveis de elementos. Este é um dos padrões mais fundamentais e reutilizáveis ​​em entrevistas de codificação. 🔹 Definição de problemas Dado um conjunto de elementos, gerar todos os subconjuntos (o conjunto de energia). 📌 Exemplo: entrada: [1, 2, 3]Saída: [[]Assim, [1]Assim, [2]Assim, [3]Assim, [1,2]Assim, [1,3]Assim, [2,3]Assim, [1,2,3]]🔹 Intuição Cada elemento tem duas opções: inclua -a no subconjunto. Exclua -o do subconjunto. 👉 Isso forma uma árvore de decisão binária, levando a subconjuntos de 2^n para n elementos. 🔹 Modelo universal para subconjuntos void backtrack (índice int, lista atual, int[] nums, lista> resultados) {if (index == nums.Length) {Results.add (novo ArrayList <> (atual)); retornar; } // 1. Exclua nums[index]
backtrack (índice + 1, corrente, nums, resultados); // 2. Inclua nums[index]
Current.add (nums[index]); backtrack (índice + 1, corrente, nums, resultados); // desfazer a escolha de Current.remove (current.size () – 1); } Digite Modo de tela cheia de saída Modo de tela cheia 🔹 Implementação de java – conjunto de energia Importar java.util.*; classe pública Subsetspattern {Lista pública> subconjuntos (int[] nums) {list> resultados = novo ArrayList <> (); backtrack (0, novo ArrayList <> (), nums, resultados); RETORNO DE RECURSOS; } backtrack de void privado (índice int, lista atual, int[] nums, lista> resultados) {if (index == nums.Length) {Results.add (novo ArrayList <> (atual)); retornar; } // exclui backtrack (índice + 1, corrente, nums, resultados); // Incluir Current.add (NUMS[index]); backtrack (índice + 1, corrente, nums, resultados); // backtrack (desfoque) current.remove (current.size () – 1); }} Digite Modo de tela Full -Screen Sair [1,2]:

[]
/ \
[] [1]

/ \ / \
[] [2] [1] [1,2]

Digite o modo de saída de tela cheia no modo de tela cheia 📌 Os caminhos representam opções → Cada folha é um subconjunto. 🔹 Variações em entrevistas subconjuntos com duplicatas Entrada: [1,2,2]

Evite subconjuntos duplicados. Use a classificação + pular duplicatas. private void backtrackdup (int start, list atual, int[] nums, lista> resultados) {Results.add (novo ArrayList <> (atual)); para (int i = start; i < nums.length; i++) {
if (i > Start && nums[i] == NUMS[i – 1]) continuar; // pular a duplicata Current.add (NUMS[i]); backTrackDup (i + 1, corrente, nums, resultados); Current.Remove (Current.size () – 1); }} Digite o modo de tela cheia de saída de tela cheia subconjuntos de tamanho K entrada: nums =[1,2,3]k = 2 saída: [ [1,2]Assim, [1,3]Assim, [2,3] ]private void backtrackk (int start, int k, lista atual, int[] nums, lista> resultados) {if (current.size () == k) {resulta.add (new ArrayList <> (atual)); retornar; } para (int i = start; i Fonte