[LeetCode] 1863. Sum of All Subset XOR Totals

문제링크

재귀를 사용해서 조합을 이용해 배열의 모든 Subset의 XOR값을 구하는 문제이다.

배열에서 특정 길이의 Subset을 만들기 위해서는 조합을 사용해야 하는데, 조합 공식은 아래와 같다.

이 공식을 사용해서 코드를 작성하면 아래와 같다.

int subset[13];
int sum;

void combination(int* nums, int n, int r, int count) {
    if(r==0) // xor 계산
    {
        int xor=subset[0];
        for(int i=1;i<count;i++)
        {
            xor ^= subset[i];
        }
        sum+=xor;
    }
    else if (n<r) return;
    else
    {
        subset[r-1]=nums[n-1];
        combination(nums, n-1, r-1, count); //(n-1)C(r-1)
        combination(nums, n-1, r, count); //(n-1)Cr
    }
}


int subsetXORSum(int* nums, int numsSize){
    sum = 0;

    for(int i=0;i<numsSize;i++)
    {
        sum+=nums[i];
    }

    for(int i=2;i<=numsSize;i++)
    {
        memset(subset, 0, sizeof(subset));
        combination(nums, numsSize, i, i);
    }

    return sum;
}