[순환] 멱집합(Powerset)

멱집합

어떤 집합 A에 대하여 A의 모든 부분 집합들로 이루어진 집합을 A의 멱집합이라고 한다.

Mission: S의 멱집합을 출력하라

powerSet(s)

if S is an empty set

   print nothing;

else

   let t be the first element of S;

   find all sudsets of S-{t} by calling powerSet(S-{t});

   print the subsets;

   print the subsets with adding t;

위 방법은 여러개의 집합들을 return해야 한다.
따라서 Recursion을 이용하면

powerSet(P, S) //S의 멱집합을 구한 후 각각에 집합 P를 합집합하여 출력하라

if S is an empty set

   print P;

else

   let t be the first element of S;

   powerSet(P, S-{t}); //t포함 X
   powerSet(P{t}, S-{t}); //t 포함 O

함수로 구현하면

	private static char data[]= {'a','b','c','d','e','f'};
	private static int n=data.length;
	private static boolean [] include = new boolean [n]; //트리상에서 현재 나의 위치를 표현한다.
	
	public static void powerSet(int k) {
		if(k==n) { //만약 내 위치가 리프노드라면
			for(int i=0;i<n;i++)
				if(include[i])	System.out.print(data[i]+" ");
			System.out.println();
			return;
		}
		include[k]=false;
		powerSet(k+1); //먼저 왼쪽으로 내려갔다가
		include[k]=true;
		powerSet(k+1); //이번엔 오른쪽으로 내려간다
	}

 

 

 

 

 

[무료] 영리한 프로그래밍을 위한 알고리즘 강좌 - 인프런 | 강의