[C++] 백준 1182 : 부분수열의 합

#include <iostream>

int N, S;
int cnt = 0;
int arr[20]; // 1 <= N <= 20

void dfs(int start, int tmp){
  if(tmp == S && start != 0){ // start != 0 - 처음 시작때 카운트하지 말 것
    cnt++;
    // 여기 return X - 계속 더해나가야 함. 여기서 분기 끊기면 안됨.
  }
  if(start == N){ // 범위 초과
    return;
  }
  for(int i = start; i < N; i++){
    dfs(i+1, tmp + arr[i]); // tmp += arr[i]로 따로 빼지 말 것. tmp 값 다른 분기까지 변동됨
  }
}

int main(int argc, char** argv){
  scanf("%d %d", &N, &S);

  for(int i=0; i<N; i++){
    scanf("%d", &arr[i]);
  }

  dfs(0, 0);
  printf("%d", cnt);
  return 0;
}

백트래킹 연습용 문제.

tmp를 따로 구한 다음에 dfs 재귀함수에 넣어 계속 틀렸다고 떠서 생각을 고치는데 너무 힘들었다ㅜㅜ
tmp값이 변화하면 다른 tmp값에도 그대로 영향을 미치기 때문에 값을 변수에 저장하지 않고 재귀함수의 매개 변수에 값을 넣어주면 된다.

그리고 start != 0 의 조건문을 넣어 tmp = 0(초기값), S = 0(주어진값), start = 0(초기값)일 때 count를 하지 않도록 하면 된다.

추가 테스트 케이스

4 -6
2 -9 -2 -6

답 : 2

5 0
0 0 0 0 0

답 : 31
(32가 아니다!!)