합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)

 

문제 풀이

해당 문제는 subset(부분집합) 을 만들어서 전체 배열의 원소의 합을 2로 나누었을 때 부분집합 의 합과 똑같으면 YES 다르면 NO 를 출력 하는 방식으로 접근 해보았다.

 

먼저 부분집합을 만드는 방식에 있어서 해당 원소를 부분집합으로 포함 할지 안할지 이렇게 2진 트리로 재귀호출을 할수 있다.

 

func SameSumSubSet(depth, sum int) {
    SameSumSubSet(depth+1, sum+array[depth])
    SameSumSubSet(depth+1, sum)
}

 

depth 와 함께 sum 이라는 변수를 재귀호출 로 넘김으로써 depth 가 N 과 같아졌을때 총합 / 2 와 비교하기 위해서 사용한다.

 

첫번째 재귀 호출은 해당원소를 부분집합으로 사용하는 재귀호출이고 두번째 재귀호출은 사용하지 않는 재귀호출이다.

if depth == N {
    if total-sum == sum {
        answer = "YES"
        flag = true
        return
    }
}

 

depth 가 N 과 같아졌을때는 total 과 비교하여 부분집합이 나머지 부분집합과 합이 일치하는지 판단하고 flag 를 true 로 바꿈으로써 더이상 재귀호출 하지않고 계속 탈출하기 위함이다.

 

package dfs

import (
	"fmt"
	"testing"
)

var N int
var array []int
var check []bool
var answer string
var flag bool
var total int

func SameSumSubSet(depth, sum int) {
	if flag {
		return
	}

	if depth == N {
		if total-sum == sum {
			answer = "YES"
			flag = true
			return
		}
	} else {
		SameSumSubSet(depth+1, sum+array[depth])
		SameSumSubSet(depth+1, sum)
	}

}

func TestSameSumSubSet(t *testing.T) {
	N = 6
	array = []int{1, 3, 5, 6, 7, 10}
	check = make([]bool, N)
	flag = false
	for _, ele := range array {
		total += ele
	}
	SameSumSubSet(0, 0)
	fmt.Println(answer)
}

 

 

전체 코드입니다.

 

이해가 안가시는 부분이 있다면 댓글로 물어봐주세요!