leetcode1863_ 2021-10-14

leetcode1863 Find the sum of all your XORs and sum them up

Law 1 ：
Each number in the array has two states: select and deselect , Set the array size to n. We use the first of an integer n Bit to simulate the selection state of each subset , The size of this integer is determined by 0( An empty set ) To (1 << n) - 1( The complete ). Then we iterate over the array , At the same time, check the bit of this integer , If 1, Just XOR on that bit ; by 0 Then skip directly .

class Solution {
    
public:
    int subsetXORSum(vector<int>& nums) {
    
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < (1 << n); ++i){
     // Every integer i It represents a subset 
            int ret = 0;
            for(int j = 0; j < n; ++j){
    
                if((i >> j) & 1) // If i Of j Position as 1, On XOR 
                ret ^= nums[j];
            }
            ans += ret; // Plus the XOR and of this subset 
        }
        return ans;
    }
};

Law two ：
We use dfs. Set the array length to n. function dfs There are three parameters ,dfs(int val, int index, nums);
val representative [0, index - 1] Exclusive or values , It is known. . and [index, n - 1] It is unknown. . Consider the index
position , There are two states: select and deselect , If selected , that val It becomes val^nums[index], If you don't select , that val = val unchanged . We make use of index == n To judge the end . Use res To maintain the sum of exclusive or subsets .

class Solution {
    
public:
    int n;
    int res;
    void dfs(int val, int index, vector<int>& nums){
    
        if(index == n){
     //index == n, Represents that you have reached the head of the array 
            res += val;
            return;
        }
   // For the two states dfs
        dfs(val^nums[index], index + 1, nums);
        dfs(val, index + 1, nums);
    }
    int subsetXORSum(vector<int>& nums) {
    
        res = 0;
        n = nums.size();

        dfs(0, 0, nums);
        return res;
    }
};