Backtracking

백트래킹은 주어진 어떤 집합에 대해 조건을 만족하는 모든 부분집합(subset)을 구하는 정형화된 알고리즘이다.

/*
  a[] : 답중 하나가 되는 부분 집합을 저장할 공간
  n : 전체 집합의 크기
  k : 현재 집합의 크기
  candidates[] : 조건들 (예, 포함되거나 안되거나)
*/
void process_solution(int a, int k)
{
  for (int i = 1; i <= k;)
    if (a[i] == 1) printf ("...", i);
}
void construct_candidates( ... c, *nc)
{
  c[...] = condition
  ...
  *nc = X; // number of conditions
  return;
}
backtrack(a[], k, n)
{
  if (k == n)
    process_solution(a, k);
  else
    k++;
    construct_candidates(c, &nc);
    for (int i = 0; i < nc; i++)
      a[k] = c[i]; // set condition
      backtrack(a, k, n);
}
int main()
{
  a = arr[MAXSIZE];
  backtrack(a, 0, n);
}