💡 백트래킹/브루트포스 알고리즘
Memory 1112KB Time 4ms Code Length 410B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
int N, S;
int sum = 0;
int result = 0;
int arr[20];
void dfs(int index)
{
if (index == N) {
if (sum == S) {
result++;
}
return;
}
sum = sum + arr[index];
dfs(index + 1);
sum = sum - arr[index];
dfs(index + 1);
return;
}
int main()
{
scanf("%d %d", &N, &S);
for (int i = 0; i < N; i++) {
scanf(" %d", &arr[i]);
}
dfs(0);
if (S == 0) result--;
printf("%d", result);
}
이 코드는 사용자로부터 N과 S를 입력받은 후, N개의 정수를 배열 arr에 저장한다. 그리고 dfs 함수를 호출하여 모든 경우의 수를 탐색하면서 합이 S가 되는 경우의 수를 센다.
dfs 함수는 재귀적으로 배열 arr의 요소를 더하거나 빼면서 모든 경우를 탐색한다. 만약 index가 N과 같아지면 현재까지의 합이 S와 같은지 확인하고, 같다면 결과값을 증가시킨다.
그리고 마지막에 S가 0이라면 결과값을 하나 감소시킨 후 결과값을 출력한다.
