2021.08.03(Tue.) <배열의 모든 부분집합 구하기>

완벽한 부분집합입니다. 그리고 피자도 완벽하죠.

1. 문제의 발단

• 요즘 보고 있는 알고리즘 문제들에 '부분집합'을 구하는 문제들이 많다. 매번 찾아보고 생각해서 쓰는 것보다 아예 외워버리듯이 적어버리면 편하지 않을까?라는 생각과 일단은 어떻게 모든 부분집합을 구할 수 있을까?라는 관점에서 포스팅을 하려고 한다.

2. 부분집합?

파란색 원은 밖의 검은선 원의 부분집합이다.

• 파란색 원은 밖의 원에 안에 있다. 이것이 바로 완전한 부분집합이 되는 것이다.
• 그러므로, 배열에서 '부분집합'을 말하면, 아래의 예시에서, arr안에 arrPartOne은 부분집합으로 모두 들어 있지만, arrPartTwo의 경우, 5가 없어서 부분집합이라고 할 수 없다.

let arr = [0, 1, 2, 3, 4]
let arrPartOne = [1, 0]
let arrPartTwo = [4, 5]

3. 그래서 어떻게 구할까?

• 재귀 함수를 이용한다.

let arr = [1, 2, 3]

let result = []

function everyComb(string, begin) {
	result.push(string);
	for(let i = begin; i < arr.length; i++) { // 반복문으로 시작점부터 arr의 요소 하나하나를 선택하고
		everyComb(string + arr[i], i + 1); // 재귀함수의 인자로 하나씩 넣어서 시작점을 1씩늘린다.
	}
}
everyComb('', 0);

console.log(result) // '', '1', '12', '123', '13', '2', '23', '3'