Why does this code return an empty array?

Question

Question: Given a collection of distinct integers, return all possible permutations.

Example: Input: [1,2,3]

Desired output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Aren't arrays passed by reference in JavaScript? Why is the result array empty when I return it?

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  var result = [];
  helper(nums, result, []);
  return result;
};

var helper = function(nums, result, cur) {
  if (cur.length == nums.length) {
    result.push(cur);
  } else {
    for (let i = 0; i < nums.length; i++) {
      cur.push(nums[i]);
      helper(nums, result, cur);
      cur.pop();
    }
  }
}
console.log(permute([1, 2, 3]));

CertainPerformance CertainPerformance · Accepted Answer · 2020-01-19T05:35:27

You only ever create a single cur array when you call helper:

helper(nums, result, []);

Which you proceed to mutate and recursively pass around in helper. There's only one array in memory; by the end, you've .popped the last item from the array, and every item in the result array refers to the same object, the now empty cur array.

Instead, clone cur inside the loop, so that when/if it gets pushed, you're pushing a new array, rather than a reference to the old one which will get reused everywhere:

for (let i = 0; i < nums.length; i++) {
  const temp = cur;
  cur = [...cur, nums[i]]; // Similar to `.push`, except it creates a new array
  helper(nums, result, cur);
  cur = temp; // Similar to `.pop` - reverts the array to what it was originally
}

var permute = function(nums) {
  var result = [];
  helper(nums, result, []);
  return result;
};

var helper = function(nums, result, cur) {
  if (cur.length == nums.length) {
    result.push(cur);
  } else {
    for (let i = 0; i < nums.length; i++) {
      const temp = cur;
      cur = [...cur, nums[i]]; // Similar to `.push`, except it creates a new array
      helper(nums, result, cur);
      cur = temp; // Similar to `.pop` - reverts the array to what it was originally
    }
  }
}

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

Why does this code return an empty array?

2 Answers