부분집합 [C언어]

문제로 풀어보는 알고리즘.

// 부분집합
#include 

void print_arr(int arr[], int arr_len)
{
  int i;
  for (i = 0; i < arr_len; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

/*
부분집합 공식
P(A) = (e*P(A')) U P(A')
e를 포함한 A' 와 e를 포함하지 않는 A'의 합집합
A'는 A' = A - {e} 라고 A에서 집합 {e}를 뺀 것.
그렇지만 코드가 좀 이해가 안된다.
*/
void subset(int set[], int set_size, int n, int index)
{
  if (index == n) {
    print_arr(set, set_size);
    return;
  }
  /*
  set[set_size]가 계속 변경됨.
  index가 올라감에 따라 set[set_size]의 기존 집합이 덮어씌워진다.
  ex) 
  set = [0 1 2] 에서 index가 오르면서
  set = [0 1]
  set = [0 2]
  뭐 이런식으로... 다른 언어였으면 그냥 set같은 걸 사용하면
  좋을 것 같다.
  */
  set[set_size] = index;  // set[size_size]로 집합을 흉내.
  subset(set, set_size+1, n, index+1);  // index(e) 포함한 경우.
  subset(set, set_size, n, index+1);  // index(e)를 포함안한 경우.
}

#define N 100
int main() {
  int set[N], n;
  printf("input n : ");
  scanf("%d", &n);
  subset(set, 0, n, 0);
  return 0;
}