javascriptalgorithmsubsetpowerset

Javascript: Array being passed as parameter doesn't retain values


I am trying to solve the problem Subsets using Javascript. The task is to print the powerset i.e., all subsets from an array. In the function below, I am passing an array as a parameter to collect all the subsets, but when I print, I find all but empty arrays only.

Why doesn't the array all_sets retain the elements? How do I modify the function parameter to retain the elements?

function generate(nums, curr_index, temp, all_sets) {
  if (curr_index === nums.length) {
    all_sets.push(temp);
    return;
  }

  temp.push(nums[curr_index]);
  generate(nums, curr_index + 1, temp, all_sets);
  temp.pop();
  generate(nums, curr_index + 1, temp, all_sets);
}

function generateAllSubsets(nums) {
  let all_sets = [];
  generate(nums, 0, [], all_sets);
  return all_sets;
}

let all_sets = generateAllSubsets([1, 2, 3, 4]);
console.log(all_sets);


Solution

  • The problem is you're pushing the reference to the temp into all_sets. Now since the same temp array gets modified in your recursive calls, it ends up being empty(when result gets constructed when the stack gets emptied in bottom up fashion) when you push it to all_sets. The fix is pretty simple. Push a copy of the temp into all_sets instead of the reference. Something like:

    function generate(nums, curr_index, temp, all_sets) {
      if (curr_index === nums.length) {
        all_sets.push([...temp]); // <--- here
        return;
      }
    
      temp.push(nums[curr_index]);
      generate(nums, curr_index + 1, temp, all_sets);
      temp.pop();
      generate(nums, curr_index + 1, temp, all_sets);
    }
    
    function generateAllSubsets(nums) {
      let all_sets = [];
      generate(nums, 0, [], all_sets);
      return all_sets;
    }
    
    let all_sets = generateAllSubsets([1, 2, 3, 4]);
    console.log(all_sets);