Sum of All Subsets XOR Total - Leetcode 1863 - Python

0:00 - Read the problem
0:30 - Drawing Explanation 1
4:45 - Coding Explanation 1
6:55 - Drawing Explanation 2
17:10 - Coding Explanation 2

leetcode 1863

#neetcode #leetcode #python

[lexkilpatrick]

How could this possibly be an easy problem when generating all subsets is a medium backtracking problem in itself 🤣

[grantpeterson]

I (somehow) managed to deduce the mathematical OR solution by myself without seeing it, and I gotta say, I'm pretty damn proud of myself

[DanielGarza]

Thank you for making this! Super helpful as these problems are quite tricky and I want to start leetcoding a bit every day.

[leo]

This is a cool problem and solution!
You have a small calculation error around 14:39, it should be 28 like you calculated right after.

[nirmalgurjar]

Thank you neetcode, was able to come up with first solution. was wondering any trick to introduce caching but since there are 2^n different possibilities so caching won't be helpful but still i have this doubt in my mind, is there any way we can introduce caching?

[ritikaagrawal]

the person who assigns difficulty level on leetcoode is probably high all the time.

[RahulJain-kkno]

How can I handle nervousness and anxiety during an interview? I messed up my last interview due to this, even though the questions that were asked weren't that difficult.

[deadlyecho]

Just build a truth table and you will understand the last solution... this will help in getting why the 50% percent ratio still the same even if we added a number with a one bit in the position we are looking at....

[koreandude]

will you have any promotions for the pro course for memorial day? struggling wannabe engineer here.

[ish]

Why did we not use memoisation in the backtracking solution ?

[EduarteBDO]

I'm bad at math and bad at bit manipulation, now lc are fusing both with these questions.

[rgolanng]

Have you ever worked with AI project in big tech yet?

[michael._.]

ngl but this bit manipulation method was pretty damn "creative"

[MohanRam-mqpk]

me findind difficult to understand O(2^n) itself 😭

[licokr]

Wow, it's crazy huh. I couldn't believe it the problem is an easy problem. it's worth it solving the problem though, I think that would be enough knowing how to work the recursive solution.

var subsetXORSum = function(nums) {
let answer = 0;

const b = (initialNums, choices) => {
let xor = 0;
for (let i = 0; i < initialNums.length; i++) {
xor ^= initialNums[i];
}
answer += xor;

while (choices.length > 0) {
b(initialNums.concat(choices.shift()), [...choices]);
}
}

b([], nums);

return answer;
};

This is my solution, which is less efficient than the solution shown up in this video. It get rid of an element from the list the func gets then will pass the new array.
I think the solution you introduced in the video has a point to understand how recursive works. Thanks for the video! 👍

--- ps

I think why it's a bit hard to understand the solution is because the concept of passing by value, the total.

In the case where nums is [5, 1, 6].

dfs(i + 1, total ^ nums[i])

i == 4 -> returns 0
0 ^ 6 + 0 ^ 1 + 0 ^ 5 + 0
(0 ^ 1) + (0 ^ 1) ^ 6 + 0
(0 ^ 5) + (0 ^ 5) ^ 1 + (0 ^ 5) ^ 6 + 0
(0 ^ 5 ^ 1) + 0

[brenocabral]

Why does the LeetCode logo look like a fancy way to pick a toothpick?

[deathbombs]

Correction- we hate math AND bit manipulation!

[pastori]

i did NOT understand this its ok tho who would expect you to come up with this