[백준][Java] 1182번 부분수열의 합 (백트래킹, 브루트포스)

 

 

(↓isChanged 패러미터 생략함)

isChanged를 지우기 위해서는 sum이 0일때 공집합의 경우를 1회 빼줘야함;;...

풀이 안 봤으면 isChanged끼고 해야 했을듯

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
    
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    private static int[] num;
    private static int S;
    private static int res;
    
    private static void bt(int tot, int pos) {
        if(pos == num.length) {
            if(tot==S)
                res++;
            return;
        }
        
        
        bt(tot+num[pos] ,pos+1);
        bt(tot, pos+1);
        
    }
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int N = stoi(str[0]);
        S = stoi(str[1]);
        res = 0;
        
        num = new int[N];
        str = br.readLine().split(" ");
        for (int i=0; i<N; i++)
            num[i] = stoi(str[i]);
        
        bt(0 , 0);
        
        res = (S==0)? --res : res;
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
    }
    
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}

 

 

 

 

(↓처음에 푼 것)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
    
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    private static int[] num;
    private static int S;
    private static int res;
    
    private static void bt(int tot, int pos, boolean isChanged) {
        if(tot == S && isChanged)
            res++;
        
        if(pos == num.length)
            return;
        
        bt(tot+num[pos] ,pos+1,true);
        bt(tot, pos+1, false);
        
    }
    
    public static void main(String[] args) throws IOException{
        String[] str = br.readLine().split(" ");
        int N = stoi(str[0]);
        S = stoi(str[1]);
        res = 0;
        
        num = new int[N];
        str = br.readLine().split(" ");
        for (int i=0; i<N; i++)
            num[i] = stoi(str[i]);
        
        bt(0 , 0, false);
        
        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
    }
    
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}