'2025/04/05'에 해당되는 글 1건

Leetcode Problem:

• Sum of All Subset XOR Totals

Summary

• The problem requires finding the sum of all XOR totals for every subset of the given array.

Approach

• The approach used is a recursive function that tries all possible subsets by either including or excluding the current element in the subset.

Complexity

• O(2^n * n) where n is the number of elements in the array

Explanation

• The solution uses a recursive function to generate all possible subsets
• For each subset, it calculates the XOR total by XORing all elements in the subset
• The base case is when the current index is out of bounds, in which case the XOR total is added to the result
• The function is called recursively with the next index and the XOR total of the current element
• The time complexity is O(2^n * n) because in the worst case, we have to generate all possible subsets and calculate the XOR total for each subset.

Solution Code:

class Solution {
public:
    int ans = 0;
    void go(int cur, int sum, vector& nums){
        if(cur >= nums.size()) {
            ans += sum;
            return;
        }
        go(cur + 1, sum ^ nums[cur], nums );
        go(cur + 1, sum, nums );
    }
    int subsetXORSum(vector& nums) {
        go(0, 0, nums);
        return ans;
    }
};