부분집합의 합

 

문제

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

1182번: 부분수열의 합

 

참고 : m.blog.naver.com/PostView.nhn?blogId=tlstjd436&logNo=221568959948&proxyReferer=https:%2F%2Fwww.google.com%2F

백준(BOJ) 1182 - 부분수열의 합 (부분집합 구하기) //[java]- 재귀

 

참고로 모두 방문하지 않은 경우는 제외해 줘야 한다.(공집합의 경우)

 

코드

package org.kyhslam.CodeUp;

import java.util.Scanner;

public class p3009_11 {

    static int[] array ; // {-7, -3, -2, 5, 8};
    static int count = 0; //

    static int N = 0;
    static int S = 0;

    static boolean[] visited;


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        S = sc.nextInt();

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

        for(int i=0; i < N; i++){
            array[i] = sc.nextInt();
        }

        for(int i=0; i < array.length; i++){
            //System.out.println(array[i]);
        }

        func(array, 0,0, visited);

        System.out.println(count);
    }



    //방문이 모두 false였을 경우, = 공집합의 경우는 제외하고 계산해야 한다.
    public static void func(int[] arr, int level, int sum, boolean[] visit){

        if(level == N){
            //모두 방문하지 않은거는 제외
            int falseCnt = 0;
            for (int i=0; i < visited.length; i++){
                if(visit[i] == false){
                    falseCnt++;
                }
            }

            if(falseCnt != N){
                if(sum == S){
                    count++;
                }
            }
        }else{
            visit[level] = true;
            func(arr, level+1, sum + arr[level], visit);

            visit[level] = false;
            func(arr, level+1, sum , visit);
        }
    }
}