LeetCode 1863. Sum of All Subset XOR Totals Solution in Java, C++, Python & More | Explanation + Code

Description

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] is 2 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.

 

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

 

Constraints:

• 1 <= nums.length <= 12
• 1 <= nums[i] <= 20

Solutions

Solution 1: Binary Enumeration

We can use binary enumeration to enumerate all subsets, and then calculate the XOR sum of each subset.

Specifically, we enumerate i in the range [0, 2ⁿ), where n is the length of the array nums. If the jth bit of the binary representation of i is 1, it means that the jth element of nums is in the current subset; if the jth bit is 0, it means that the jth element of nums is not in the current subset. We can get the XOR sum of the current subset according to the binary representation of i, and add it to the answer.

The time complexity is O(n × 2ⁿ), where n is the length of the array nums. The space complexity is O(1).

PythonJavaC++GoTypeScriptRustJavaScript

class Solution: def subsetXORSum(self, nums: List[int]) -> int: ans, n = 0, len(nums) for i in range(1 << n): s = 0 for j in range(n): if i >> j & 1: s ^= nums[j] ans += s return ans(code-box)

class Solution { public int subsetXORSum(int[] nums) { int n = nums.length; int ans = 0; for (int i = 0; i < 1 << n; ++i) { int s = 0; for (int j = 0; j < n; ++j) { if ((i >> j & 1) == 1) { s ^= nums[j]; } } ans += s; } return ans; } }(code-box)

class Solution { public: int subsetXORSum(vector<int>& nums) { int n = nums.size(); int ans = 0; for (int i = 0; i < 1 << n; ++i) { int s = 0; for (int j = 0; j < n; ++j) { if (i >> j & 1) { s ^= nums[j]; } } ans += s; } return ans; } };(code-box)

func subsetXORSum(nums []int) (ans int) { n := len(nums) for i := 0; i < 1<<n; i++ { s := 0 for j, x := range nums { if i>>j&1 == 1 { s ^= x } } ans += s } return }(code-box)

function subsetXORSum(nums: number[]): number { let ans = 0; const n = nums.length; for (let i = 0; i < 1 << n; ++i) { let s = 0; for (let j = 0; j < n; ++j) { if ((i >> j) & 1) { s ^= nums[j]; } } ans += s; } return ans; }(code-box)

impl Solution { pub fn subset_xor_sum(nums: Vec<i32>) -> i32 { let n = nums.len(); let mut ans = 0; for i in 0..(1 << n) { let mut s = 0; for j in 0..n { if ((i >> j) & 1) == 1 { s ^= nums[j]; } } ans += s; } ans } }(code-box)

/** * @param {number[]} nums * @return {number} */ var subsetXORSum = function (nums) { let ans = 0; const n = nums.length; for (let i = 0; i < 1 << n; ++i) { let s = 0; for (let j = 0; j < n; ++j) { if ((i >> j) & 1) { s ^= nums[j]; } } ans += s; } return ans; };(code-box)

Solution 2: DFS (Depth-First Search)

We can also use depth-first search to enumerate all subsets, and then calculate the XOR sum of each subset.

We design a function dfs(i, s), where i represents the current search to the ith element of the array nums, and s represents the XOR sum of the current subset. Initially, i=0, s=0. During the search, we have two choices each time:

• Add the ith element of nums to the current subset, i.e., dfs(i+1, s \oplus nums[i]);
• Do not add the ith element of nums to the current subset, i.e., dfs(i+1, s).

When we have searched all elements of the array nums, i.e., i=n, the XOR sum of the current subset is s, and we can add it to the answer.

The time complexity is O(2ⁿ), and the space complexity is O(n). Where n is the length of the array nums.

PythonJavaC++GoTypeScriptRustJavaScript

class Solution: def subsetXORSum(self, nums: List[int]) -> int: def dfs(i: int, s: int): nonlocal ans if i >= len(nums): ans += s return dfs(i + 1, s) dfs(i + 1, s ^ nums[i]) ans = 0 dfs(0, 0) return ans(code-box)

class Solution { private int ans; private int[] nums; public int subsetXORSum(int[] nums) { this.nums = nums; dfs(0, 0); return ans; } private void dfs(int i, int s) { if (i >= nums.length) { ans += s; return; } dfs(i + 1, s); dfs(i + 1, s ^ nums[i]); } }(code-box)

class Solution { public: int subsetXORSum(vector<int>& nums) { int n = nums.size(); int ans = 0; auto dfs = [&](this auto&& dfs, int i, int s) { if (i >= n) { ans += s; return; } dfs(i + 1, s); dfs(i + 1, s ^ nums[i]); }; dfs(0, 0); return ans; } };(code-box)

func subsetXORSum(nums []int) (ans int) { n := len(nums) var dfs func(int, int) dfs = func(i, s int) { if i >= n { ans += s return } dfs(i+1, s) dfs(i+1, s^nums[i]) } dfs(0, 0) return }(code-box)

function subsetXORSum(nums: number[]): number { let ans = 0; const n = nums.length; const dfs = (i: number, s: number) => { if (i >= n) { ans += s; return; } dfs(i + 1, s); dfs(i + 1, s ^ nums[i]); }; dfs(0, 0); return ans; }(code-box)

impl Solution { pub fn subset_xor_sum(nums: Vec<i32>) -> i32 { fn dfs(i: usize, s: i32, nums: &[i32], ans: &mut i32) { if i == nums.len() { *ans += s; return; } dfs(i + 1, s, nums, ans); dfs(i + 1, s ^ nums[i], nums, ans); } let mut ans = 0; dfs(0, 0, &nums, &mut ans); ans } }(code-box)

/** * @param {number[]} nums * @return {number} */ var subsetXORSum = function (nums) { let ans = 0; const n = nums.length; const dfs = (i, s) => { if (i >= n) { ans += s; return; } dfs(i + 1, s); dfs(i + 1, s ^ nums[i]); }; dfs(0, 0); return ans; };(code-box)