연향동큰손

문제 이해문제수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.입력첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.출력첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다. 주의할 점 : 수열 S를 이루고 있는 숫자가 100,000보다 작거나 같은 자연수, 수열의 크기는 최대 20 ==> 수열의 합으로 ..

문제 이해 주어진 수열의 부분수열의 합이 S가 되는 경우의 수를 구해주면 되는 문제이다.모든 경우의 수를 집고 넘어가야 하므로 dfs를 이용하면 쉽게 풀 수 있다. 문제 풀이 private static void dfs(int start, int sum){ if(start==N) { if (sum == S) { count++; } return; } dfs(start+1,sum+num[start]); dfs(start+1,sum);}  배열에서 선택된 수를 더할지 아니면 그냥 넘어갈지를 결정하기 위해서 재귀 호출을 이용하였다. 그리고 start변수가 N이 되면 배열의 끝까지 도달한 경우인데 이때의 sum이 S와 같으면 경우의 수에..