Sponsored
Sponsored
This approach uses recursion to generate all possible subsets of the array and calculates their XOR sum. The function will explore each element, either including or excluding it in the subset. This will give us the XOR sum for each subset, and we can accumulate the total from there.
Time Complexity: O(2n), where n is the length of nums.
Space Complexity: O(n) because of the recursion stack.
1public class SubsetXorSum {
2 public static void main(String[] args) {
3 int[] nums = {1, 3};
4 System.out.println(subsetXORSum(nums)); // Output: 6
5 }
6
7 public static int subsetXORSum(int[] nums) {
8 return xorSubsetSum(nums, 0, 0);
9 }
10
11 private static int xorSubsetSum(int[] nums, int index, int currentXor) {
12 if (index == nums.length) {
13 return currentXor;
14 }
15 int include = xorSubsetSum(nums, index + 1, currentXor ^ nums[index]);
16 int exclude = xorSubsetSum(nums, index + 1, currentXor);
17 return include + exclude;
18 }
19}This Java solution recursively computes the XOR sum for all subsets by choosing to include or exclude each number. The total XOR sum is returned by accumulating results from recursive calls.
The alternative approach involves using bit manipulation to generate subsets efficiently. Each number's inclusion in a subset corresponds to a binary decision, allowing us to loop from 0 to (2n - 1) integers, using each binary representation as a decision for a subset.
Time Complexity: O(n * 2n), where n is the length of nums due to the bitwise operations.
Space Complexity: O(1) as no additional space is used apart from counters.
1
This Python function calculates the XOR sum for each subset using a bitmask approach. Each position in the binary representation of mask dictates inclusion in the subset.