[DataStructure&Algorithm] 부분집합,멱집합 SubSet, powerSet

jangwonyoon·2021년 4월 4일
0

알고리즘

목록 보기
9/10

부분집합과 멱집합 알고리즘

Backtracking1 (체크 배열 사용)

let subsets = function(nums) {
    let result = [];
    let n = nums.length;
    let ch = Array.from({length:n} , ()=>0);
    
    const dfs = (L) => {
        if(L===n) {
            let tmp = [];
            for(let i=0; i<n; i++) {
                if(ch[i] === 1) tmp.push(nums[i]);
            }
            result.push(tmp);
        }else {
            ch[L] = 1;
            dfs(L+1);
            ch[L] = 0;
            dfs(L+1)
        }
    }
    dfs(0);
    return result;
};

Backtracking2

let subsets = function(nums) {
	let res = []
	backtrack(0, [])
	
	function backtrack(index, curr) {
		res.push(curr)
		for (let i = index; i < nums.length; i++) {
			backtrack(i + 1, [...curr, nums[i]])
		}
	}
	
	return res
}

Lexicographic Subsets (비트연산자)

let subsets = function(nums) {
    let res = []
    const powSize = Math.pow(2, nums.length)

    for (let i = 0; i < powSize; i++) {
        let set = []
        for (let j = 0; j < nums.length; j++) {
            if ((i & (1 << j)) > 0) {
                set.push(nums[j])
            }
        }
        res.push(set)
    }
    return res
}
profile
어제보다 오늘 더 노력하는 프론트엔드 개발자

0개의 댓글