[문제풀이] 08-01. 합이 같은 부분집합

인프런, 자바(Java) 알고리즘 문제풀이

DFS, BFS 활용 - 0801. 합이 같은 부분집합(DFS : 아마존 인터뷰)

---

🗒️ 문제

---

🎈 나의 풀이

	private static int[] use;
    private static int DFS(int[] arr, int i) {
        if(i >= arr.length) return 0;
        int sum1 = 0;
        int sum2 = 0;

        if(i > 0) {
            for (int k = 0; k < arr.length; k++) {
                if (use[k] == 0) sum1 += arr[k];
                if (use[k] == 1) sum2 += arr[k];
            }
        }
        if(sum1 == sum2 && i > 0) return 1;

        use[i] = 1;
        int a = DFS(arr, i+1);
        use[i] = 0;
        int b = DFS(arr, i+1);

        return a + b;
    }
    private static String solution(int[] arr) {
        if(DFS(arr, 0) > 0) return "YES";
        return "NO";
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        use = new int[n];

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

        System.out.println(solution(arr));
    }

---

🖍️ 강의 풀이

  	static String answer="NO";
	static int n, total=0;
	boolean flag=false;
	public void DFS(int L, int sum, int[] arr){
		if(flag) return;
		if(sum>total/2) return;
		if(L==n){
			if((total-sum)==sum){
				answer="YES";
				flag=true;
			}	
		}
		else{
			DFS(L+1, sum+arr[L], arr);
			DFS(L+1, sum, arr);
		}
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++){
			arr[i]=kb.nextInt();
			total+=arr[i];
		}
		T.DFS(0, 0, arr);
		System.out.println(answer);
	}

---

💬 짚어가기

해당 문제는 DFS를 이용하여 풀 수 있다. 나의 풀이에서는 use라는 배열을 두고,
집합을 담은 배열에서 해당 인덱스에 담긴 요소의 사용 여부를 보관하도록 하였다.

그 다음 해당 인덱스를 사용하는 경우와 그렇지 않은 두 가지 경우를 나눠 DFS를
수행하고, 그 때 사용되는 요소들의 합과, 나머지 요소들의 합이 같은지 판별하도록
구현하여 문제를 해결했다.

강의에서는 따로 체크 배열을 두지 않고, 호출 함수의 파라미터로 누적합 값과 현재
바라보는 인덱스를 넘기도록 하였다. 누적합에 현재 인덱스를 더하는 경우와 그렇지
않은 두 가지 경우를 나눠 DFS를 수행한다.

만일 현재 바라보는 인덱스가 주어진 배열 요소의 개수와 동일한 경우, 문제의 조건을
만족하는지 검사한다. 전체 요소를 합한 값과 누적합의 차의 결과가 누적합의 크기와
동일한 경우 YES를 반환한다.

추가로

이미 문제를 만족하는 경우 이거나, 누적합이 전체 요소의 합의 절반 크기를 넘어서는
경우 바로 리턴하도록 구성하여 실행 시간을 단축시킨다.