백트래킹

가능한 모든 경우의 수를 다 수행해보는 것

브루트포스와 다른 점은

특정 조건에 해당하는 경우에만 탐색을 진행

대표적인 문제 15649 : N과M(1)

int n, m;
int arr[10];
bool isused[10];

void func(int k) { //현재까지 k개의 수를 선택함
	if (k == m) { //m개를 모두 선택했으면
		for (int i = 0; i < m; i++) {
			cout << arr[i] << ' '; //배열에 기록해둔 수들을 출력
		}
		cout << '\n';
        return;
	}
	for (int i = 1; i <= n; i++) { //1부터 n까지의 수에대해
		if (!isused[i]) { //아직 i가 사용되지 않았으면
			arr[k] = i; //k번째에 i를 넣어주고
			isused[i] = 1; //i를 사용했다고 남겨주고
			func(k + 1); //다음 수를 정하러 재귀를 한차례 더 들어감
			isused[i] = 0; //k번째수를 i로 정한 모든 경우에 대해 다 확인했으니 i를 다시 사용하지 않았다고 표시해줌
		}
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	func(0);
}

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0C/15649.cpp