인프런 커뮤니티 질문&답변

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

연속부분수열 문제를 dfs로 풀려고 하는데 답이 이상하게 나옵니다. 가지치기로 배열의 숫자들을 선택해서 더할때, 선택안하고 넘어갈 때 2가지로 구분해서 풀었습니다.

아니면 혹시 연속된 수열이라서 dfs로는 못 푸는 건가요??

import java.util.*;

public class Main {

public static int n,m,answer;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n=sc.nextInt();

m=sc.nextInt();

int[] num = new int[n];

for(int i=0; i<n; i++)

num[i]=sc.nextInt();

dfs(0,0,num);

System.out.print(answer);

}

public static void dfs(int L, int sum, int[] a) {

if(sum>m) return;

if(L==n) {

if(sum==m) answer++;

}

else {

dfs(L+1, sum+a[L], a);

dfs(L+1, sum, a);

}

}

}