완전검색 그리디 - 부분 집합

1. 부분 집합

• 집합에 포함된 원소들을 선택하는 것입니다.
• 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것입니다.
  • 예) 배낭 짐 싸기(knapsack)
• N개의 원소를 포함한 집합
  • 자기 자신과 공집합 포함한 보든 부분집합(power set)의 개수는 2ⁿ개
  • 원소의 수가 증가하면 부분집합의 개수는 지수적으로 증가

---

2. 부분 집합 생성 방법

• 바이너리 카운팅을 통한 사전적 순서(Lexicographic Order)
  • 부분집합을 생성하기 위한 가장 자연스러운 방법입니다.
  • 바이너리 카운팅(Binary Counting)은 사전적 순서로 생성하기 위한 가장 간단한 방법입니다.