leetcode: 1863. Sum of All Subset XOR Totals

문제링크

풀이1

[5, 1, 6]

• count : 1
  • [5], [1], [6]
• count : 2
  - [5, 1], [5, 6], [1, 6]
• count : 3
  - [5, 1, 6]

class Solution {
    private fun dfs(nums: IntArray, subset: MutableList<Int>, count: Int, start: Int): Int {
        if (subset.size == count) return subset.reduce { acc, element -> acc xor element }
        
        var result = 0
        for (i in start until nums.size) {
            subset.add(nums[i])
            result += dfs(nums, subset, count, i + 1)                
            subset.remove(nums[i])
        }
        return result
    }
    
    fun subsetXORSum(nums: IntArray): Int {
        val size = nums.size
        var answer = 0
        for (i in 1..size) {
            answer += dfs(nums, mutableListOf<Int>(), i, 0)
        }
        return answer
    }
}

풀이2

[5, 1, 6]

• (0, 0)
• (1, 5), (1, 1), (1, 6)
• (2, 5^1), (2, 5^6), (2, 1^6)
• (3, 5^1^6)

import java.util.*

class Solution {
    fun subsetXORSum(nums: IntArray): Int {
        var answer = 0
        val stack = Stack<Pair<Int, Int>>()
        stack.push(Pair(0, 0)) // index, result
        
        while (stack.isNotEmpty()) {
            val (index, result) = stack.pop()
            answer += result
            for (i in index until nums.size) {
                stack.push(Pair(i + 1, nums[i] xor result))
            }
        }
        return answer
    }
}

풀이3

[5, 1, 6]

• 5 -> 5^1 -> 5^1^6 -> 5^6
• 1 -> 1^6
• 6

class Solution {
    var answer = 0
    fun subsetXORSum(nums: IntArray): Int {
        acuumulateSubsetSum(nums, 0, 0)
        return answer
    }
    
    private fun acuumulateSubsetSum(nums: IntArray, index: Int, result: Int) {
        answer += result
        
        for (i in index until nums.size) {
            acuumulateSubsetSum(nums, i + 1, result xor nums[i])
        }
    }
}