[leetcode][416] Partition Equal Subset Sum

 문제 : leetcode.com/problems/partition-equal-subset-sum/

---

양의 정수로 이루어진 nums 배열이 주어질 때, 동일한 배열 합을 가지는 두 개의 배열로 분리시킬 수 있는지 구하라.

---

nums 배열의 합을 구한다.

동일한 배열 합을 가질 수 있다는 뜻은 배열 합이 짝수라는 뜻이다. 따라서 만약 홀수라면 false를 반환한다.

배열 합 / 2를 nums 배열을 탐색하면서 요소들의 합으로 만들 수 있는지 판단하고 만들 수 있으면 true, 아니면 false를 반환한다.

nums 배열 요소들의 합으로 sum/2 를 구할 수 있는지는 배낭 문제로 풀 수 있다.

dp[i][j] = nums[0~i]개의 요소들로 부분집합을 만들 때, 그 요소들의 합으로 j를 만들 수 있는지 여부.

dp[i][j] = i-1개의 요소들로 j로 만들 수 있거나 i-1개의 요소들로 j-nums[i]을 만들 수 있는 경우
         = dp[i-1][j] or dp[i-1][j-nums[i]]

점화식은 위와 같고 nums 배열 길이를 N. nums 배열 합 / 2를 M이라 한다면

시간복잡도는 O(NM)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/416.%20Partition%20Equal%20Subset%20Sum.cpp