[1182] 부분수열의 합

https://www.acmicpc.net/problem/1182

---

import java.util.Scanner;

// 1182 부분수열의 합
public class Main {
	static int dep;
	static int N, S, sum, cnt;
	static int [] arr, ans;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		S = sc.nextInt();
		arr = new int[N];
		ans = new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		for(int i=1; i<=N; i++) {
			dep = i;
			recur(0, 0);
		}
		System.out.println(cnt);
	}
	
	public static void recur(int start, int depth) {
		if(depth == dep) {
			sum = 0;
			for(int i=0; i<dep; i++) {
				sum += ans[i];
				System.out.print(ans[i] + " ");
			}
			System.out.println();
			if(sum == S) cnt++;
			return;
		} else {
			for(int i=start; i<N; i++) {
				ans[depth] = arr[i];
				recur(i+1, depth+1);
			}
		}
	}
}

---

완전탐색, 브루트포스 문제이다. N의 값이 20까지 밖에 안되기 때문에 반복문 2개를 이용해서 풀 수 있을 것 같았다. 근데 나는 전에 어렵게 풀었던 [6603] 로또 문제와 거의 똑같기 때문에 백트래킹을 연습하기 위해 백트래킹을 이용해서 해결했다. 메인 함수에서 입력을 받고 dep 이 1부터 N까지 탐색하면서 dep 의 수 만큼 숫자를 뽑아서 더해서 S와 같은지 검사하면서 답을 구했는데, 내가 여기서 실수한 부분 때문에 문제 해결에 시간이 오래걸렸다. 반복문을 1 부터 N 까지 돌면서 dep을 변화시켜야 하는데 0부터 N-1까지 돌면서 dep을 바꿔서 1개의 숫자가 입력으로 들어 올 때랑, 배열의 모든숫자가 S와 같을 때 카운트가 되지 않았다. dep은 숫자를 몇개 고르는지 뜻하는 변수기 때문에 이 점을 확실히 해야 겠다.

< 문제 풀이 >

1.  숫자를 1부터 N개까지 뽑으면서 모두 더해서 그 숫자가 S와 같은지 판단해서 같으면 cnt 를 증가시킨다.

2. dep 은 숫자를 몇개 뽑을지를 나타내는 변수 이기 때문에 배열의 0부터 N-1까지 넣었다고 dep 을 0부터 N-1 까지 변화시키면 안된다는 점을 주의해야 한다. dep은 1부터 N까지 변화시켜야 한다.