아마존 인터뷰
합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)
합이 같은 부분집합(DFS : 아마존 인터뷰) - (golang)
2022.05.28문제 풀이 해당 문제는 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 와 비교하기 위해서 사용한다. 첫번째 재귀 호출은 해당원소를 부분집합으로 사용하는 재귀호출이고 두번..