Problem Summary

You are given an integer array nums.
Your task is to compute the sum of XOR of every possible subset of nums.

Formally:
For all subsets S of the array, compute
xor(S)
and return the sum of all these values.

Example
Input: nums = [1,3]
Subsets are:
[] -> 0
[1] -> 1
[3] -> 3
[1,3] -> 1 ^ 3 = 2
Sum = 0 + 1 + 3 + 2 = 6

Output: 6

Constraints

• 1 ≤ nums.length ≤ 12
• 1 ≤ nums[i] ≤ 20
• Number of subsets = 2ⁿ ≤ 4096 (small enough for backtracking)

---

Approach (Simple English)

Every subset contributes one number to the final sum:
the XOR of its elements.

The simplest and most natural solution is:

• Generate all subsets (2ⁿ of them).
• Compute XOR value for each subset.
• Add to the total sum.

This works fine because n ≤ 12.

There are two standard approaches:

1. Backtracking
2. Bitmask enumeration

The backtracking method is easier to read and typical in interviews.

---

Approach 1: Backtracking (DFS)

Use a recursive function that:

• Either includes nums[i] in the subset
• Or excludes it

While carrying a running XOR value.

Key Idea

Each choice multiplies possibilities by 2, giving 2ⁿ subsets.

At each recursive call:

dfs(i, currentXor)

If at the end (i == nums.length):
    add currentXor to global sum

Why This Works

You explore all subsets and accumulate the XOR contribution of each.
Since n ≤ 12, maximum operations = 4096 recursive leaves.

Time complexity: O(n * 2ⁿ)
Space complexity: O(n) recursion depth.

---

Java Code (Backtracking)

class Solution {

    private int total = 0;

    public int subsetXORSum(int[] nums) {
        dfs(nums, 0, 0);
        return total;
    }

    private void dfs(int[] nums, int index, int xorValue) {
        if (index == nums.length) {
            total += xorValue;
            return;
        }

        // Include nums[index]
        dfs(nums, index + 1, xorValue ^ nums[index]);

        // Exclude nums[index]
        dfs(nums, index + 1, xorValue);
    }
}

Simple and clear solution.

---

Approach 2: Bitmask Enumeration (Iterative)

There are exactly 2ⁿ subsets.
Use numbers from 0 to 2ⁿ - 1 as bitmasks:

• If bit j is 1 → include nums[j]
• Else → exclude

Java Code

class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length;
        int total = 0;

        int subsetCount = 1 << n;

        for (int mask = 0; mask < subsetCount; mask++) {
            int xor = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    xor ^= nums[i];
                }
            }
            total += xor;
        }

        return total;
    }
}

Both approaches are valid.

---

Dry Run (Backtracking Approach)

Input:

nums = [1, 3]

Call dfs(0, 0):

1. Include 1
   dfs(1, 1)
   • Include 3 → dfs(2, 2) → total += 2
   • Exclude 3 → dfs(2, 1) → total += 1
2. Exclude 1
   dfs(1, 0)
   • Include 3 → dfs(2, 3) → total += 3
   • Exclude 3 → dfs(2, 0) → total += 0

Sum: 2 + 1 + 3 + 0 = 6

---

Complexity Analysis

Time: O(n × 2ⁿ)
Space: O(n)

Given constraints (n ≤ 12), this is optimal.