[2024] day 142. leetcode 1863. Sum of All Subset XOR Totals

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 20일 (월)
Leetcode daily problem

1863. Sum of All Subset XOR Totals

https://leetcode.com/problems/sum-of-all-subset-xor-totals/?envType=daily-question&envId=2024-05-20

Problem

배열의 XOR 합계는 모든 요소의 비트별 XOR로 정의되며, 배열이 비어 있으면 0이다.

예를 들어 배열 [2,5,6]의 XOR 합계는 2 XOR 5 XOR 6 = 1이다.
nums 배열이 주어지면 nums의 모든 하위 집합에 대한 모든 XOR 합계의 합계를 반환한다.
참고: 동일한 요소가 포함된 하위 집합은 여러 번 계산되어야 한다.

b의 일부(0일 수도 있음) 요소를 삭제하여 b에서 a를 얻을 수 있는 경우 배열 a는 배열 b의 하위 집합이다.

Solution

Backtracking

해당 문제는 주어진 정수 배열의 모든 부분집합의 XOR 값을 합하는 문제로, 주어진 배열의 부분집합을 생성하기 위해서 백트래킹이나 비트마스킹을 사용한다.
각 원소를 포함하거나 포함하지 않는 두 가지 선택지를 통해 모든 부분집합을 만들고 이를 탐색하면서 XOR 연산의 성질을 이용해서 각 원소가 포함된 부분집합에서 XOR 연산을 수행한다.

Code

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        
        def gen_subset(nums, idx, subset, subsets):
            if idx == len(nums):
                subsets.append(subset[:])
                return
            
            subset.append(nums[idx])
            gen_subset(nums, idx+1, subset, subsets)
            subset.pop()
            
            gen_subset(nums, idx+1, subset, subsets)
            
        
        subsets = []
        gen_subset(nums, 0, [], subsets)
        
        result = 0
        for subset in subsets:
            subset_XOR_total = 0
            for num in subset:
                subset_XOR_total ^= num
                
            result += subset_XOR_total
            
        return result

Complexicity

시간 복잡도

각 요소를 하위집합으로 만드는 재귀 함수 로직에서 배열의 각 원소에 대해 도가지 선택(포함하거나 포함하지 않거나)가 있으므로 O(2^n) 이 소요되고,
각 subsets 배열에 2^n개의 부분집합이 저장되는데, 해당 부분집합에 대해 XOR 합을 계산하는데 부분집합의 평균 길이가 n/2 이다.
따라서 XOR 합은 O(2^n * n) 이 소요된다.

그래서 전체 시간복잡도는 O(2^n * n)이다.

공간 복잡도

부분집합을 저장하는 배열에 2^n개의 부분집합이 저장되고, 부분집합의 평균 길이는 n/2로, 차지하는 공간은 O(2^n n) 이다.
또한 재귀호출의 최대 깁이는 n이고, 각 호출마다 새로운 부분집합을 생성하기 위해 O(n)이 필요하므로, 전체 공간 복잡도는 O(2^n n) 이다.