SWEA2817_부분 수열의 합

1

구분: 부분 집합

언어: Java

전략

• 부분 집합을 만든다
• 각 숫자가 포함되었는지, 안되었는지 확인한다.  by boolean array - 포함하면 true, 포함안하면 false
• 현재 '나'를 포함하고 재귀를 통해 그 다음 단계를 진행
• 현재 '나'를 뺴고, 재귀를 통해 그 다음 단계를 진행
• '나' 가 마지막 요소까지 다 포함/불포함 여부를 결정했다면 부분집합의 값들을 더해 조건과 비교
• 함수를 종

 

---

2.코드

import java.util.*;
public class Solution {
 
    //전체 숫자들을 받을 배열
    static int[] arr;
    //숫자의 포함 여부를 확인하는 배열
    static boolean[] check;
    //받는 숫자의 개수
    static int n;
    //타겟 숫자
    static int k;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
         
        for(int test_case = 1; test_case<=T; test_case++) {
            n = scanner.nextInt();
            k = scanner.nextInt();
            arr = new int[n];
            check = new boolean[n];
            //숫자 배열에 넣는다 
            for(int i = 0; i<n; i++) {
                arr[i] = scanner.nextInt();
            }
             
            subset(0);
             
            System.out.println("#"+test_case+" "+count);
            count = 0;
        }//test
 
    }//main
    //전체 개수가 몇개인지 확인
    static int count=0;
    //부분집합을 만드는 함수
    public static void subset(int cnt) {
        //이제 그만!
        if(cnt == n) {
            int sum = 0;
            for(int i = 0; i<n; i++) {
                if(check[i]) {
                    sum+=arr[i];
                }
            }if(sum==k)count++;
            return;
        }
        //나를 포함해 - 그리고 그 다음꺼 진행
        check[cnt] = true;
        subset(cnt+1);
         
        //윗줄이 끝나야 실행 
        //나를 뺴- 그리고 그 다음꺼 진행
        check[cnt] = false;
        subset(cnt+1);
         
    }
 
}

---

3 

• 기본적인 부분 집합을 구하는 문제이다
• 전체 요소의 개수가 20이하이기 때문에 모든 부분 집합을 구하는 것이 가능
• 시간 복잡도를 줄일 수 있는 다른 방법이 있다.