부분 집합을 구하는 문제가 왜 (이진) 트리 문제로 접근이 가능할까?

위의 이미지처럼 루트 노드가 있다고 가정하고, 각각의 원소가 부분집합에 포함여부를 나열하면 트리 구조로 표현할 수 있다. 가장 마지막의 노드(말단 노드)로 가는 경우의 수가 모든 부분집합의 수가 된다.