[재귀함수, 완전탐색] 합이 같은 부분집합

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

 

📖 문제 설명 : N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하는지 판단

 

💡 배열의 전체 합을 이용한다. 두 개의 부분집합의 원소가 같다는 것은 결국 집합의 원소 총합이 하나의 부분 집합의 뺀 결과의 값이 부분 집합의 값과 같다는 것이다.

재귀 함수를 이용해서 각각의 요소를 포함하는 경우, 포함하지 않는 경우로 나누어 판단한다.

 

let flag = false // 합이 같은지 판단 변수
function recursion(arr, i, sum, total) {
  if (flag) return

  if (i >= arr.length) {
    if (total - sum === sum) {
      flag = true
    }
    return
  }

  recursion(arr, i + 1, sum + arr[i], total)
  recursion(arr, i + 1, sum, total)
}

function solution(a) {
  let answer = false
  let arr = [...a]
  let total = [...a].reduce((a, b) => a + b, 0)
  // 배열, 시작 인덱스, 총합
  recursion(arr, 0, 0, total)
  answer = flag
  return answer
}

let a = [1, 3, 5, 6, 7, 10]
console.log(solution(a))

👨‍💻 코드 설명

1. 재귀 함수를 이용하여 배열을 순차적으로 순회하며 해당 요소를 포함하는 경우, 포함하지 않는 경우로 나눈다.

 

2. baseCase i가 배열의 모든 요소를 순회했을 때(하나의 집합이 완성되었을 경우) 총합 - 부분 집합 값 = 부분 집합 값인지 판단한다.

 

3. 부분 집합 값을 찾은 경우, 전역 flag 변수로 해당 결과를 반환하고 나머지 재귀 함수 로직은 종료한다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.