백트래킹은 한정 조건을 가진 문제(Constraint Satisfaction Problem ; 제약 충족 문제)를 풀려는 전략이다.

이미 지나쳐온 곳을 다시 돌아가서 다른 가능성을 시도해보는 걸 반복하는 기법 !

브루트포스는 꼭 '깊이'나 '탐색'의 개념이 아니더라도,

모든 경우의 수를 다 대입해보는 것이기 때문에 다른 개념이다

조건에 맞지 않는 경우들을 배제해가며,

모든 조합을 하나씩 시도해서 문제의 해를 찾는다

보통 재귀 함수로 구현이 되고

DFS와 비슷하게 스택을 쓰는 경우가 많지만, 기억 공간은 덜 차지한다

( 아래 의사코드 11, 13 Line

• 퇴각하며 "apply"했던 "value"를 다시 "remove"하여 돌려놓음

-> 조건 초기화 ※중요※ )

의사코드는 다음과 같다

void findSolutions(n, other params) :
	if (found a solution) :
		solutionsFound = solutionsFound + 1; //Found 개수
		displaySolution();
		if (solutionsFound >= solutionTarget) : //개수 목표치
			System.exit(0);
		return

	for (val = first to last) :
		if (isValid(val, n)) :
			applyValue(val, n);
			findSolutions(n+1, other params);
			removeValue(val, 

백트래킹을 이용한 문자 배열 문제를 보자

#include <stdio.h>
#include <string.h>

void swap(char *x, char *y)
{
	char temp;
	temp = *x;
	*x = *y;
	*y = temp;
}

void permute(char *str, int l, int r)
{
	if (l == r)
		printf("%s\\n", str);
	else
	{
		for (int i = l; i <= r; i++)
		{
			swap((str+l), (str+i));
			permute(str, l+1, r);
			swap((str+l), (str+i)); //백트래킹
		}
	}
}

int main()
{
	char str[] = "ABC";
	int n = strlen(str);

	permute(str, 0, n-1);

	return 0;
}