[LC] 416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/

Approach

0/1 knapsack 문제이다. 단, knapsack의 capacity 내에서 담을 수 있는 물건의 최대 가치를 구하는 것이 아닌, capacity와 동일한 값의 total sum을 달성할 수 있는지 여부를 구해야 한다.

이때, knapsack의 capacity는 주어진 nums의 총합의 절반이다.

만약 nums의 총합이 홀수라면 절반으로 나누어떨어지지 않으므로 빠르게 False를 리턴하자!

Idea 1: 2D DP

다음과 같이 0/1 knapsack 상황을 정의할 수 있다.

knapsack의 capacity sum(nums) // 2

objective capacity와 동일한 값의 total sum을 달성하기


knapsack의 capacity	`sum(nums) // 2`
objective	capacity와 동일한 값의 total sum을 달성하기

dp[i][j] = nums의 i번째 원소까지 봤을 때, 그 합이 j인 조합이 존재하는지 여부로 정의하고, 다음과 같은 로직으로 값을 채워나간다.

i번째 물건(= nums[i - 1])이 배낭의 임시 용량 j보다 같거나 작다면, i번째 물건을 아예 넣을 수 없으므로 i - 1번째 물건까지 살펴본 결과를 그대로 반영해야 한다.
그렇지 않다면, i번째 물건을 넣지 않는 경우와 넣는 경우 중 하나라도 가능한지 확인하면 된다.

target = total // 2

# dp[i][j] = nums의 i번째 원소까지 봤을 때, 그 합이 j인 조합이 존재하는지 여부
# j == 0: 합이 0인 조합은 모든 물건에서 가능하다! (안 넣으면 됨)
dp = [[True] + [False] * target for _ in range(n + 1)]

for i in range(1, n + 1):           # -- 값 (배낭에 넣을 물건)
  for j in range(1, target + 1):  # -- 합 (배낭의 임시 용량)
      # i번째 물건(= nums[i - 1])이 배낭의 임시 용량 j보다 같거나 작다면, i번째 물건을 아예 넣을 수 없으므로
      # i-1번째 물건까지 살펴본 값을 넣음
      if nums[i - 1] > j:
          dp[i][j] = dp[i - 1][j]
      # 그렇지 않다면, i번째 물건을 넣지 않는 경우와 넣는 경우 중 하나라도 가능한지 확인
      else:
          dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]

return dp[n][target]

Idea 2: 1D DP (Space Optimized)

2D DP에서 이전 row(dp[i - 1])의 값(dp[i - 1][j] 혹은 dp[i - 1][j - nums[i - 1]])만 필요했으므로, 1D DP로 space-optimize가 가능하다.

단, dp[i - 1]의 [j] 혹은 [j - nums[i - 1]]와 같이 이전 인덱스를 확인해야하므로, 오른쪽 -> 왼쪽 순으로 순회해야 한다.

또한, j를 순회할 때, dp 테이블을 그대로 재사용하기 때문에 현재 보고 있는 물건의 무게 num 이상인 값까지만 순회해도 되므로 time 측면에서도 약간 optimize가 되지 않을까 싶다!

target = total // 2

# dp[j] = nums의 i번째 원소까지 봤을 때, 그 합이 j인 조합이 존재하는지 여부
dp = [False] * (target + 1)
dp[0] = True

for num in nums:                          # -- 값 (배낭에 넣을 물건)
    for j in range(target, num - 1, -1):  # -- 합 (배낭의 임시 용량): 현재 넣으려는 물건 무게의 이상인 값만 보면 된다!
        dp[j] = dp[j] or dp[j - num]

return dp[target]

Idea 3: 다른 풀이 방법

ref: sol1, sol2

bit mask, DFS 등 다양한 방법으로도 풀 수 있는 듯.

이건 나중에 복습할 때 알아보자..

🔍 Knapsack Problem

0/1 knapsack만 조금 풀어봤었는데 다른 유형들도 풀어봐야겠다...

0/1 Knapsack vs. Fractional Knapsack

구분	특징	풀이 방법
0/1 knapsack	item을 쪼갤 수 X	dynamic programming
fractional knapsack	item을 쪼갤 수 O	greedy

Bounded vs. Unbounded

구분	특징
bounded	item 당 수량이 정해져 있음
unbounded	item 당 수량이 무한 개

References

Complexity

Time: O(n * sum)
Space: (2D DP) O(n * sum) / (1D DP) O(sum)

seungriyou / algorithm-study