Início / coding / Perguntas / 79594534
Accepted
Will Sherman
Asked: 2025-04-27 07:55:24 +0800 CST

Problema de JavaScript com permutações recursivas retornando array vazio

  • 772

Um problema de permutações (LeetCode), que encontra as permutações de um array [1,2,3], retorna um array vazio por meio de uma função recursiva de retrocesso. O console imprime o seguinte:

Input
nums =
[1,2,3]
Stdout
[ [ 1, 2, 3 ] ]
[ [ 1, 3, 2 ] ]
[ [ 2, 1, 3 ] ]
[ [ 2, 3, 1 ] ]
[ [ 3, 1, 2 ] ]
[ [ 3, 2, 1 ] ]
Output
[[]]

Esta seria a solução adequada se o array não parecesse ser reinstanciado em cada chamada recursiva.

Aqui está o código:

    /**
 * @param {number[]} nums
 * @return {number[][]}
 */

var permute = function(nums) {
    let s = [], a = [];
    return findPerm(nums, s, a);
   
};

var findPerm = function(nums, stack, ans){
    if(nums.length === stack.length){
        if(ans.indexOf(stack) === -1)
            ans.push(stack);
      
      console.log(ans);
    }

    for(let num of nums){
        if(stack.indexOf(num) === -1){
            stack.push(num);
            findPerm(nums, stack, ans);
            stack.pop();
        }
    }
    return ans;
};

permute([1,2,3]);

Por que estou recebendo um array vazio?

javascript

1 respostas

  1. Best Answer

    Isso acontece porque você está enviando stackpara ans, mas também modificando a mesma stackreferência de array posteriormente com stack.pop(), fazendo com que o array enviado pareça vazio. Uma maneira de corrigir isso seria fazer uma cópia do stackarray ao enviá-lo para ans:

    ans.push(stack.slice());

    agora, quando você .pop(), ele não modificará mais esta nova referência de array.

    const permute = function(nums) {
  const s = [], a = [];
  return findPerm(nums, s, a);

};

const findPerm = function(nums, stack, ans) {
  if (nums.length === stack.length) {
    ans.push(stack.slice());
  }

  for (let num of nums) {
    if (stack.indexOf(num) === -1) {
      stack.push(num);
      findPerm(nums, stack, ans);
      stack.pop();
    }
  }
  return ans;
};

console.log(permute([1, 2, 3]));

    • 0

relate perguntas