[C] LeetCode 1863. Sum of All Subset XOR Totals

 

문제

번역

배열의 XOR Total 이라는 것은 배열의 모든 원소에 대해 XOR을 한 것을 말합니다. 

만약 배열이 비어있다면 XOR Total은 0이 됩니다.

 

nums라는 정수 배열이 주어졌을 때, nums의 모든 부분 배열의 XOR Total의 합을 반환해라.

- 동일한 원소를 가진 부분배열은 동시에 카운트될 수 있습니다. 

접근 방법 및 소스 코드

입력의 길이를 \(n\)이라고 하자.

그러면 subset은 총 \(2^n\) 개가 생긴다.

 

즉, 각 원소마다 선택지가 2개가 생긴다.

해당 원소를 집어넣으면 기존 값과 xor을 하고, 해당 원소를 집어넣지 않으면 기존 값을 그대로 가져간다.

이를 그냥 재귀로 돌려주고 더해주면 끝이다.

물론 종료조건은 배열의 끝까지 가면 xor을 반환해주면 된다.

 

int recursive(int* nums, int n, int index, int xor) {
    if(index >= n) return xor;
    return recursive(nums, n, index+1, xor) + recursive(nums,n,index+1, xor ^ nums[index]);
}

int subsetXORSum(int* nums, int numsSize) {
    return recursive(nums, numsSize,0,0);    
}