[Java Algorithm Note] 부분집합 (feat. 재귀)

드디어 순열, 조합, 부분집합 시리즈 중 마지막인 부분집합 등쟝

(순열, 조합 정리는 아래를 참고해주세요! 👇)

https://seolhee2750.tistory.com/229

[Java Algorithm Note] 순열 (feat. 재귀)

https://seolhee2750.tistory.com/230

[Java Algorithm Note] 조합 (feat. 재귀)

 

📎 부분집합

부분집합은 중복도 가지지 않고, 순서도 가지지 않으며 최대 r개를 뽑아 나열하는 것을 말한다.

 

순열과 조합은 모두 정해진 개수만큼만 뽑아 나열하였다.

하지만 부분집합의 경우 원하는 개수'까지'의 모든 경우의 수를 뽑아 나열한다.

(3개를 입력하면 0개일 때부터 3개일 때까지를 모두 고려!)

 

예를 들어 {1, 2, 3}이 주어지면

{}, {1}, {2}, {3}, {1, 2}, ..., {1, 2, 3} 이렇게!!

---

📎 부분집합 구현

 

public class SubSet {
	
	static char[] src = { 'a', 'b', 'c', 'd' };
	
	/*
     * 부분 집합: 중복 X, 순서 X
     * @param toCheck - 선택될 수 있는 요소의 인덱스
     * @param checked - 선택된 요소들의 자리를 true로 표현
     */
	static void powerSetDupPer(int toCheck, boolean[] checked) {
        if(toCheck == checked.length) { // 기저 조건: choosed를 다 채웠다면 끝
        	print(checked);
        	return;
        }
        
        // toCheck에 해당하는 요소를 선택할 것인지 안할 것인지
        checked[toCheck] = true;
        powerSetDupPer(toCheck+1, checked);
        checked[toCheck] = false;
        powerSetDupPer(toCheck+1, checked);
    }

    static void print(boolean[] temp) {
    	List<Character> selected = new ArrayList<>();
    	List<Character> unselected = new ArrayList<>();
    	for(int i = 0; i < temp.length; i++) {
    		if(temp[i]) selected.add(src[i]);
    		else unselected.add(src[i]);
    	}
        System.out.println(selected + " : " + unselected);
    }
    
	public static void main(String[] args) {
		System.out.println("부분집합");
        powerSetDupPer(0, new boolean[3]); // src로 구성 가능한 최대 3개의 모든 부분집합 출력
	}

}

checked 배열에 선택한 요소는 true로 처리해주어 선택했음을 표시하는 식으로 구현했다.

boolean형태의 checked 배열을 완성하면, print 메서드를 이용해서 집합을 출력했다.

---

👀 정리

부분 집합은 선택한 개수 내에서 가능한 모든 조합을 의미한다.

부분 집합 또한 순열과 조합처럼 재귀로 구현할 수 있는데,

0개부터 n개까지의 모든 경우를 체크해주어야 하므로,

바로 배열에 값을 담지 않고 boolean으로 체크해준 뒤 값을 따로 출력하는 식으로 작성했다.