[백준 1182] 부분 수열의 합 - Java

문제링크: https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

---

문제설명

 

문제접근

0번째 인덱스부터 차례로 해당 인덱스의 값을 더하는 경우와 더하지 않는 경우 두 가지로 나눠 탐색을 진행하면

풀 수 있습니다. 이 때 중복 확인을 방지 하기 위해 더하지 않는 경우는 타겟 S와 비교하지 않고 넘어갑니다.

 

 

소스코드

package ps.boj;
 
import java.util.Scanner;
 
/**
 *  @문제접근
 *  완전탐색으로 풀었습니다.
 *
 *  @성능
 *  Runtime: 120 ms
 *  Memory Usage: 14296 KB
 *  시간복잡도: O(2^N)
 */
 
public class BOJ_1182_부분수열의합 {
    public static int answer = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int n = sc.nextInt(), s = sc.nextInt();
        sc.nextLine();
 
        int[] arr = new int[n];
 
        for(int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
 
        System.out.println(solve(arr, s));
    }
 
    public static int solve(int[] arr, int target){
 
        dfs(0, 0, target, arr, false);
 
        return answer;
    }
 
    private static void dfs(int idx, int now, int target, int[] arr, boolean isAdd) {
        if(isAdd && now == target)
            answer++;
 
        if(idx == arr.length)
            return;
 
        dfs(idx + 1, now + arr[idx], target, arr, true);
        dfs(idx + 1, now, target, arr, false);
    }
}