📖 완전검색(부분집합, 조합)

📌 부분집합(Powerset)

✅ 부분집합의 수

• 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개

• 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.

✅ 반복문을 이용하여 부분집합 구하기

sel = {0, 0, 0, 0}
for i in 0 to 1:
	sel[0] = i
    for j in 0 to 1 :
    	sel[1] = j
        for k in 0 to 1 :
        	sel[2] = k
            for l in 0 to 1 :
            	sel[3] = l
                print(sel)

✅ 비트마스킹을 이용하여 부분집합 구하기

// N : 원소의 개수
// 부분집합의 수 만큼 반복 돌리기
for(int i=0; i<<(1<<N); i++) {
	// i라는 부분집합에 원소 확인하기
    for(int j=0; j<N; j++) {
    	// 해당 i 값에 j번째 비트가 존재한다면..
        if((i & (1 << j)) > 0) }
        	// 처리
        }
    }
}

✅ 재귀 호출을 이용하여 부분집합 구하기

// sel[] : 해당 원소 포함 여부 저장
// n : 원소의 개수, k : 현재 depth
static void powerset(int n, int k) {
	// Basis Part
    if(n == k) { 
    	print(sel);
        return;
    }
    
    // Indeuctive Part
    sel[k] = false;
    powerset(n, k+1);
    sel[k] = true;
    powerset(n, k+1);
}

📌 조합 (Combination)

✅ 재귀 호출을 이용한 조합 생성 알고리즘

// data[] : n개의 원소를 가지고 있는 배열
// sel[] : r개의 크기의 배열, 조합이 임시 저장될 배열
// sidx : sel 배열의 인덱스
// idx : data 배열의 인덱스

comb(idx, sidx)
	IF sidx == r : print_array()
    ELSE IF idx >= n : RETURN
    ELSE
    	sel[sidx] <- data[idx]
        comb(idx+1, sidx+1)
        comb(idx+1, sidx)

✅ 반복문을 이용한 조합 생성 알고리즘

// {1, 2, 3, 4} 중 원소 3개를 뽑아보자

for i from 1 to 2 {
	for j from i+1 to 3 {
    	for k from j+1 to 4 {
        	print i, j, k;
        }
    }
}

✅ 반복문 + 재귀를 이용한 조합 생성 알고리즘

// data[] : n개의 원소를 가지 고 있는 배열
// sel[] : r개의 크기의 배열
// idx : data 배열의 인덱스

comb(idx, sidx) 
	IF sidx == r : print_array()
    ELSE
    	FOR i from idx to N-R+sidx
        	sel[sidx] <- data[i]
            comb(i+1, sidx+1)