Sum of All Subset XOR Totals

Link

https://leetcode.com/problems/sum-of-all-subset-xor-totals/

Deadline

Dec 16, 2021

Status

Archived

Type

Backtracking

문제

풀이

재영

조합으로 풀어씁니다유 🙂


/**
 * @param {number[]} nums
 * @return {number}
 */

function combinations(arr, num) {
    const resArr = [];
    if (num === 1) return arr.map(val => [val]);
    arr.forEach((now, nowIdx) => {
        const restArr = arr.filter((each, eachIdx) => nowIdx < eachIdx);
        const cArr = combinations(restArr, num - 1);
        const result = cArr.map(c => [now, ...c]);
        resArr.push(...result);
    });

    return resArr;
}

var subsetXORSum = function(nums) {
    let res = 0;
    for (let i = 1; i <= nums.length; i += 1) {
        const nowResult = combinations(nums, i);
        nowResult.forEach((nowArr) => {
            let total = 0;
            nowArr.forEach((val) => {
                total = total ^ val;
            })
            res += total;
        })
    }
    return res
};

오랜만에 돌아온 은찬 - 오 반가워요~~~ 은찬넴~~~


const subsetXORSum = (nums) => {
    let answer = 0;
    
    const getXor = (array) => {
        let xor = array[0];
        
        for(let i = 1; i < array.length; i++){
            xor ^= array[i];
        }
                
        return xor;
    }
    
    const dfs = (start, array) => {
        answer += getXor(array);
        
        if(start >= nums.length){
            return;
        }
        
        
        for(let i = start; i < nums.length; i++){
            dfs(i + 1, [...array, nums[i]]);
        }
    }
    
    for(let i = 0; i < nums.length; i++){
        dfs(i + 1, [nums[i]]);
    }
    
    return answer;
};