Problem
The XOR total of an array is defined as the bitwise XOR
of all its elements, or 0
if the array is empty.
- For example, the XOR total of the array
[2,5,6]
is2 XOR 5 XOR 6 = 1
.
Given an array nums
, return the sum of all XOR totals for every subset of nums
.
Note: Subsets with the same elements should be counted multiple times.
An array a
is a subset of an array b
if a
can be obtained from b
by deleting some (possibly zero) elements of b
.
Examples
Example 1:
|
|
Example 2:
|
|
Example 3:
|
|
Solution
Method 1 - Using backtracking
This problem is very similar to subsets problem, where we generate subset of all elements in array, just that we xor
the elements. We may exclude or include the element when we are doing dfs on nums
:
Approach
- At each step, decide whether to include or exclude the current element in the subset.
- Use recursive calls to compute the XOR totals for both possibilities:
- Include the current number (take XOR).
- Skip the current number (ignore XOR).
- For every subset explored, accumulate the XOR total into a running sum.
- Base case handles when we’ve reached the end of the array.
Video explanation
Here is the video explaining this method in detail. Please check it out:
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(2^n)
. For an array of sizen
, there are (2^n) subsets. This is because each element in the array has two choices: to be included in the subset or not.- Each recursive call processes one subset, and there are (2^n) recursive calls in total.
- 🧺 Space complexity:
O(n)
. The recursion goes as deep as the length of the arraynums
. Each recursive call adds a frame to the call stack.