Was working on this leetcode question: https://leetcode.com/problems/subsets/
and came up with this solution:
INPUT = [1, 2, 3]
var subsets = function(nums) {
let ans = []
for (let num of nums) {
// DUPLICATE ARRAY
ans = [...ans, ...ans]
const size = ans.length
// ITERATE THROUGH LAST HALF OF ARR
for (let i = size / 2; i < size; i ) {
ans[i].push(num) <------------- THIS AINT RIGHT :(
}
ans.push([num])
}
return [[], ...ans]
};
ANS = [[],[1,2,3,3],[1,2,3,3],[2,3],[1,2,3,3],[1,2,3,3],[2,3],[3]] (INCORRECT)
However, it seemed to be incorrectly pushing values in multiple indexes for some reason. After fiddling around with the code thinking my logic is correct, I came up with this:
var subsets = function(nums) {
let ans = []
for (let num of nums) {
// DUPLICATE ARRAY
ans = [...ans, ...ans]
const size = ans.length
for (let i = size / 2; i < size; i ) {
ans[i] = [...ans[i], num] <--------------- THIS WORKS
}
ans.push([num])
}
return [[], ...ans]
};
ANS = [[],[1],[1,2],[2],[1,3],[1,2,3],[2,3],[3]] (correct)
And that ended up working... Why is this happening? Doesn't arr[i].push(num)
pretty much equal the same thing as arr[i] = [...arr[i], num]
CodePudding user response:
The reason is that the subarrays are not copied when you do:
ans = [...ans, ...ans]
This merely produces the same subarray references. This means that when you push
unto one of the subarrays in the second half of ans
, you'll see the effect also via the first half of ans
, as both halves reference the same subarrays.
So to solve this, make a deeper copy when producing the second half:
ans = [...ans, ...ans.map(arr => Array.from(arr))]
The second, working version, performs this deeper copy in the line that you marked.