1863. Sum of All Subset XOR Totals

문제 요약

• 알고리즘 분류:  백트레킹, 수학, 배열
• 난이도: Medium
• 문제내용:
  • 수 배열 nums가 주어진다.
  • XOR 총합(XOR total)은 배열의 모든 요소를 비트 단위 XOR 연산한 값이며, 배열이 비어 있는 경우에는 0으로 정의한다.
    • [2, 5, 6]의 XOR 총합은 2 XOR 5 XOR 6 = 1 이다.
  • 정수 배열 nums가 주어질 때, nums의 모든 부분집합에 대한 XOR 총합의 합을 구하여 반환하여라
• 사이트 주소: https://leetcode.com/problems/sum-of-all-subset-xor-totals/description/

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://jih3508.tistory.com/84

[알고리즘 이론] 백트래킹(Backtracking)

접근 방법 

  이번 문제에서는 백트레킹에서 조합 구현만 하면 되는 문제이다. 구현하는 방법은 아래 같이 하면된다.

1. 총합을 0으로 초기화 한다.
2.  아래와 같은 재귀 호출할 함수 만든다.
   • 파라미터를 nums 시작할 위치와, 부분 집합 담을 리스트를 만든다.
   • 부분 집합 리스트 XOR을 연사하고 총합에 더한다.
   • 시작할 위치가 nums 크기이상일때 return한다.
   • 시작할 위치부터  nums 크기까지 탐색한다.
   • i번째 nums를 부분집합에 추가하고 재귀호출 한다.
   • 이전 재귀 호출 끝나면 부분집합 맨 끝 부분을 제거한다.
3. nums 시작할 위치 0 빈 리스트로 재귀 호출한다.

 이번 문제는 백트레킹에서 조합 응용하는 문제이다. 많이 나오는 유형이다. 백트레킹으로 조합것은 외워 두면 유용할 것이라고 생각한다.

Code

Python

class Solution:
    def __init__(self):
        self.result = 0 # 최종 XOR 합을 저장할 변수

    def subsetXORSum(self, nums: List[int]) -> int:
        size = len(nums) # 배열 nums의 길이

        def subset(index, arr: List[int]):
            xor_sum = 0
            # 현재 배열 arr의 모든 요소를 XOR 연산 후 result에 추가
            for num in arr:
                xor_sum ^= num
            self.result += xor_sum

            # 배열의 크기가 원본 배열 크기와 같아지면 재귀 종료
            if index >= size:
                return

            # idx부터 시작하여 부분집합을 구성
            for i in range(index, size):
                arr.append(nums[i]) # 현재 요소 추가
                subset(i + 1, arr) # 재귀 호출하여 다음 요소 탐색
                arr.pop() # 백트래킹을 위해 마지막 요소 제거

        self.result = 0
        # 0번째 index와 빈 배열로 시작
        subset(0, [])

        return self.result

Combintion

파이썬에서는 itertools에 combinations제공한다. combinations사용하면 따로 재귀 호출 구현 할 필요 없다.

from itertools import combinations

class Solution:

    def subsetXORSum(self, nums: List[int]) -> int:
        size = len(nums) # 배열 nums의 길이

        result = 0 # 최종 XOR 합을 저장할 변수
        for i in range(1, size + 1):
            for arr in combinations(nums, i): # i 크기만큼 조합
                xor_sum = 0
                # 현재 배열 arr의 모든 요소를 XOR 연산 후 result에 추가
                for num in arr:
                    xor_sum ^= num
                result += xor_sum

        return result

 

Java

class Solution {
    int sum; // 최종 XOR 합을 저장할 변수
    int size; // 배열 nums의 길이
    int[] nums;

    public int subsetXORSum(int[] nums) {

        this.sum = 0;
        this.size = nums.length;
        this.nums = nums;

        // 0번째 index와 빈 배열로 시작
        subset(0, new LinkedList<>());

        return this.sum;
    }

    public void subset(int idx, List<Integer> arr){
        // 현재 배열 arr의 모든 요소를 XOR 연산 후 sum에 추가
        this.sum += arr.stream().reduce(0,(a,b)->a^b);

        // 배열의 크기가 원본 배열 크기와 같아지면 재귀 종료
        if(idx >= this.size){
            return;
        }

        // idx부터 시작하여 부분집합을 구성
        for (int i = idx; i < this.size; i++) {
            arr.add(this.nums[i]); // 현재 요소 추가
            subset(i+1, arr); // 재귀 호출하여 다음 요소 탐색
            arr.remove(arr.size()-1); // 백트래킹을 위해 마지막 요소 제거
        }
    }
}

Javascript

var subsetXORSum = function(nums) {
    
    let sum = 0; // 최종 XOR 합을 저장할 변수
    const size = nums.length; // 배열 nums의 길이

    const xorSum = (idx, arr) => {
        // 현재 배열 arr의 모든 요소를 XOR 연산 후 sum에 추가
        sum += arr.reduce((a, b) => a ^ b, 0);

        // 배열의 크기가 원본 배열 크기와 같아지면 재귀 종료
        if (arr.length === size) {
            return;
        }

        // idx부터 시작하여 부분집합을 구성
        for (let i = idx; i < size; i++) {
            arr.push(nums[i]); // 현재 요소 추가
            xorSum(i + 1, arr); // 재귀 호출하여 다음 요소 탐색
            arr.pop(); // 백트래킹을 위해 마지막 요소 제거
        }
    }

    // 0번째 index와 빈 배열로 시작
    xorSum(0, []);

    return sum;
};