7.2.1, 7.2.2

main.py

"""
# 문제 7.2: 동일 합으로 배열 분할 문제

양의 정수로 구성된 배열이 주어지면, 해당 배열을 두 부분으로 분할하여 동일한 합의 값을 가지는지 확인해보라.
예를 들어서, [1, 2, 3, 4]가 있고 [1, 4], [2, 3]으로 분할하면 각 분할된 배열 요소의 합이 5로 동일하다.

### 아이디어 (Brute-Force)

1. 배열의 전체 합을 2로 나눈다.
2. 전체 합이 2로 나눈 나머지가 0이 아니라면 바로 거짓(False)을 반환
3. 배열의 인덱스를 하나씩 증가시키며 전체 합을 반으로 나눈 값보다 현재 인덱스 값이 작다면 해당 값을 포함하여 재귀 호출을 한다.
  - 반환값이 참(True)일 때, 바로 참(True)을 반환한다.
4. 재귀 호출 복귀 후에 해당 인덱스 값을 포함하지 않고 재귀 호출을 한다.

### 아이디어 (동적 프로그래밍 - Top Down)

1. 전체 탐색에서 중복된 연사을 저장하기 위한 공간을 생성한다.
  - 초기값 - 1
  - 전체 탐색에서 변화된 값은 참조 인덱스와 합의 값
2. dp[배열 최대 인덱스][누적 합] 이 -1이 아니면 해당 값을 반환한다.
3. dp[배열 최대 인덱스][누적 합]으로 구성하여 매 재귀 호출을 진행하며 dp 배열 결과를 구성
4. 최종 dp[n-1][s]를 반환한다.

### 아이디어 (동적 프로그래밍 - Bottom Up)

0. dp[n-1[s+1]을 모두 False로 초기화 한다.
1. 생성된 2차원 배열 (0,0)에서부터 누적합의 1/2까지 순회한다.
  - 배열의 숫자를 포함하지 않고 dp[i-1][s]의 값이 이미 확인된 상태(True) 라면 dp[i][s]도 같은 값으로 업데이트
  - 현재 순회 값(s)이 num[i] 보다 크다면, dp[i - 1][s - num[i]]의 결과를 dp[i][s]에 적용한다.
2. dp[n-1][s] 반환
"""
from typing import List


def can_partition(nums: List[int]) -> bool:
    if sum(nums) % 2 != 0:
        return False

    def can_partition_recursive(nums: List[int], s, index):
        if s == 0:
            return True
        if index >= len(nums):
            return False

        if s - nums[index] >= 0:
            if can_partition_recursive(nums, s - nums[index], index + 1):
                return True
        return can_partition_recursive(nums, s, index + 1)

    return can_partition_recursive(nums, int(sum(nums) / 2), 0)


def can_partition2(nums: List[int]) -> bool:
    """
    Top-Down 방식
    :param nums: 
    :return: 
    """
    s = sum(nums)
    if s % 2 != 0:
        return False

    def can_partition_recursive(dp: List[int], nums: List[int], s, index):
        if s == 0:
            return 1

        if index >= len(nums):
            return 0

        if dp[index][s] == -1 and nums[index] <= s:
            if can_partition_recursive(dp, nums, s - nums[index], index + 1) == 1:
                dp[index][s] = 1
                return 1
        dp[index][s] = can_partition_recursive(dp, nums, s, index + 1)
        return dp[index][s]

    dp = [[-1 for _ in range(int(s / 2) + 1)] for _ in range(len(nums))]
    return True if can_partition_recursive(dp, nums, int(s / 2), 0) == 1 else False