Find permutation of array – Where am I going wrong?

So we have an array and I need to find all the permutation of the items in it.

for e.g, arr = [1, 2] should return [[1, 2], [2,1]]

Now here’s my thought process:

If the array is empty, it should return [] which gives me the base condition.

if(arr.length === 0) return [];

Now we can further break the problem like this:

permutation([item1, item2]) = [[item1, ...permutation(item2)], [item2, ...permutation(item1)]

// permutation([1, 2, 3]) = [[1, ...permutation(2,3)], [2, ...permutation(1,3)], [3, ...permutation(1,3)]

So with that I tried to code:

function findPermutation(arr){

  function permute(arr){
    if(arr.length === 0) return [];//empty array base condition
    var res= [];
    for(let el of arr){
      //Reducing the array
      var filteredArray = arr.filter(a=> a!== el);
      //taking recursive leap of faith
      var temp = permute(filteredArray);
      res.push([el, ...(temp)])
    }
    
    //I suspect the problem could be here. It doesn't result
   //correctly so final output remains incorrect
    return res;
  }
  
  return permute(arr);
}
console.log(findPermutation([1, 2, 3]))

But somehow I’m making some mistakes in returning the res which is resulting in giving wrong results.

Where am I going wrong and is the above thought process correct?

>Solution :

The approach which you’re following is correct. However, there needs a slight modification in your implementation. So, when you push the element into the res array, you need to push it into an array combined with each of the sub-permutations returned by the permute(filteredArray) call. One way to achieve this is by using a nested loop.

function findPermutation(arr) {
  function permute(arr) {
    if (arr.length === 0) return [
      []
    ]; // Return array with an empty array

    const res = [];
    for (let el of arr) {
      const filteredArray = arr.filter(a => a !== el);
      const subPermutations = permute(filteredArray);

      // note the below loop
      for (let subPermutation of subPermutations) {
        res.push([el, ...subPermutation]);
      }
    }

    return res;
  }

  return permute(arr);
}

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