백준 1182 부분수열의 합(Java)

 

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

1182번: 부분수열의 합

 

---

 

해석 및 팁

 

---

 

이 문제는 백트래킹문제로 dfs 함수를 만들어서 사용하면 됩니다. 다만 주어진 s 가 0인경우에는 공집합도 포함이 되므로 1을 빼주어야 합니다. dfs함수 내부에서는 숫자를 선택하거나 선택하지 않는 두 가지 경우의 수로 풀면 됩니다.

 

---

 

Java 코드

 

---

import java.util.Scanner;

public class Main {

  static int n;
  static int s;
  static int count;
  static int[] arr;
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    count = 0;
    n = sc.nextInt();
    s = sc.nextInt();
    arr = new int[n];

    for(int i = 0; i < n; i++) arr[i] = sc.nextInt();

    dfs(0, 0);

    if(s == 0) count -= 1; 
      
    System.out.println(count);
  }

  public static void dfs(int dep, int sum) {
    if(dep == n) {
      if(sum == s) count++;
      return;
    }

    dfs(dep + 1, sum + arr[dep]);
    dfs(dep + 1, sum);
  }
}