멱집합이란?
주어진 집합의 모든 부분집합들로 구성된 집합!
n개의 값으로 구성된 집합의 모든 부분집합의 개수는 2의 n승 개이다.
{a, b, c, d}라는 집합의 멱집합을 구하는 방법은
이렇게 손으로 할 수있고,
위의 그림을 재귀함수를 사용해서 구할 수 있다
간단하게 코드를 짜봤는데
powerSet함수를 재귀적으로 호출한다.
이 함수의 매개변수를 보면 첫번째로 arr를 받는데,
이 arr는 재귀함수가 한루프 돌때마다 부분집합을 구성하는 값들이 들어있다.
그리고 두번째 매개변수는 집합의 값에 접근하기 위한 index정보를 받는다.
const numArr = ['a', 'b', 'c', 'd'];
function powerSet(arr, index) {
if (index === numArr.length) {
console.log(arr);
return;
}
// 해당 index번쨰 값을 부분집합에 포함한 후 재귀함수 호출
powerSet(arr.concat(numArr[index]), index + 1);
// 해당 index번째 값을 부분집합에 포함하지 않고 재귀함수 호출
powerSet(arr, index + 1);
}
powerSet([], 0);
2021.2.1 추가
같이 스터디하시는 분이 내 코드에서 개선점을 찾아서 말씀해 주셨다.
내 코드와 기본적인 로직은 같지만,
매개변수명이 훨씬 명확하고, 함수명에 따라 받아야할 매개변수를 잘 설정하셨다.
내 코드를 보면 powerSet([], 0) 이렇게 호출했었는데,
빈 배열과, 인덱스를 인수로 받는것보다는
부분집합을 만들 집합을 인수로 넣어주는게 의미상 명확?하다고 하셨다.
powerSet([1,2,3]) 이렇게!
역시..클린코드 장인.....
function powerSet(arr) {
const result = [];
function findPowerSet(currentArr, currentIndex) {
if (currentIndex === arr.length) {
return result.push(currentArr);
}
findPowerSet(currentArr.concat(arr[currentIndex]), currentIndex + 1);
findPowerSet(currentArr, currentIndex + 1);
}
findPowerSet([], 0);
return result;
}
console.log(powerSet([1,2,3]))개발자도구 콘솔에서 실행시킨 결과
위와 같이 잘 출력이된다
