99 삐약 : 백준 1182 | 부분 수열의 합 [바킹독| 백트래킹 |JAVA]

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

 

 

package BKD_0x0C_BackTracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1182 {
    static int N,S;
    static int[] arr= new int[30];
    static int count=0;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        func(0,0);
        if(S==0) count--; // 왜 인지 포스팅 할 때 생각해보기
        System.out.println(count);

    }

    static void func(int cur, int sum){
        if(cur == N){
            if(sum == S){
                count++;
            }
            return;
        }

        func(cur+1,sum);
        func(cur+1,sum+arr[cur]);


    }
}

 

 

 

---

 

 

 

처음 풀이를 진행 할 때는 Base Condition을 sum==S일 때로만 지정하고 진행.

현재 index 이후의 값들만 취급하여 부분 수열을 찾으려 시도. 

-> 중복된 부분 집합에 대해서 탐색하지 않아 불필요한 호출 진행

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int S;
    static int[] arr;
    static boolean[] visited;

    static int count=0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());

        arr = new int[N];
        visited  = new boolean[N];

        st = new StringTokenizer(br.readLine());

        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        func(0,arr[0]);
        System.out.println(count);

    }

    static void func(int idx, int sum){
        if(sum == S){
            count++;
            return;
        }

        for(int i=idx;i<N;i++){
            if(visited[i]) continue;
            visited[i] =true;
            func(i,sum+arr[i]);
            visited[i] = false;
            
        }
    }
}

 

 

 

❗️❗️더할지 말지를 결정한다!! ❗️❗️

함수 정의

• func(int cur, int sum) : 부분 수열의 합을 계산하는 함수

 

Base Condition : 

• cur ==N

 

Recursion

• 현재 수를 더하지 않고 부분 수열의 합을 구할 때  : func(cur+1, sum)
• 현재 수를 더하여 부분 수열의 합을 구할 때  : func(cur+1, sum+arr[cur])