Difficulty: Easy
This question being an easy question is the biggest lie told on leetcode to date.
The first idea that you think of would be to collect all the subsets of the array and iterate through it, adding the total XOR of each subset to a total sum. This is a brute force solution and would take O(2^n) time complexity, which is not ideal.
However, due to the maximum length of the array for this problem being 12, we can use this brute force solution to get the answer.
One way we can generate all the subsets is to use recursion. We keep track of the current list of subsets and the current index. At each index, we add the number to all the existing subsets. This makes a new list of subsets that we XOR and add to the total sum.
We continue this process until we process every number in the array.
I hate this question and the optimal solution uses bit manipulation that is 100% not in the scope of a leetcode Easy, hence, the first line of this file.
class Solution(object):
def subsetXORSum(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def get_total(subsets, index):
total = 0
curr_val = nums[index]
new_subsets = [subset + [curr_val] for subset in subsets]
for subset in new_subsets:
res = 0
for num in subset:
res ^= num
total += res
if index < len(nums) - 1:
total += get_total(subsets + new_subsets, index + 1)
return total
return get_total([[]], 0)Time Complexity:
O(2^n)Space Complexity:
O(2^n)Time Taken:
11m 44s