416. Partition Equal Subset Sum

1. 문제

1-1. 원문

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100

1-2. 내용 번역

배열 nums가 주어졌을 때, nums 내의 수들을 서브셋 내의 수들의 합이 같도록 2개의 서브셋으로 나눌 수 있는지의 여부를 리턴해라.

2. 문제 이해

2-1. 내용 이해

Example1을 예로 설명해보면, nums 내의 숫자들의 합은 1+5+11+5 = 22 이다. nums 내의 숫자들을 2그룹으로 나누어서 각 그룹 안의 수의 합이 11이 될 수 있으면 true, 없으면 false를 리턴해야한다. nums 내의 숫자들을 가지고 [1, 5, 5]와 [11]인 서브셋 2개를 만들 수 있고, 각 서브셋의 합이 11이 되므로 Example1의 결과는 true 가 된다.

2-2. 접근법 생각

가방의 무게는 nums 숫자 총 합의 절반, 물건의 무게는 nums 내의 각 인덱스에 저장된 숫자, 물건의 가치는 따로 없고 가방의 무게가 물건의 무게와 같아질 수 있는지의 여부로 대신한다.

초기 엣지 케이스가 있는데 배열의 크기가 1이면 이것을 합의 절반의 서브셋 둘로 나눌 수 없기 때문에 false이고, nums의 총 합이 2로 나누어떨어지지 않아도 서브셋으로 나눌 수 없기 때문에 false 이다.

2-3. 적용한 풀이

Knapsack BottomUp (Tabulation)

3. 구현

class Solution {
    fun canPartition(nums: IntArray): Boolean {
        return bottomUp(nums)
    }

    fun bottomUp(nums: IntArray): Boolean {
        var halfTotal = 0

        for(num in nums) {
            halfTotal += num
        }

        if (halfTotal%2 == 1 || nums.size == 1) return false
        halfTotal /= 2

		// 배열은 [nums 인덱스 숫자] * [현재 까지 총 합] = (현재 까지 총 합을 이전의 nums를 조합해서 만들어 낼 수 있는가의 여부)
        val memo = Array(nums.size){Array(halfTotal+1){false}}

		// 현재 까지 총 합이 0 이면 nums 인덱스 숫자를 포함시키지 않아도 되므로 항상 true
        for (i in 0..nums.size-1) {
            memo[i][0] = true
        }

		// 인덱스 0은 이중 for문에 끼지 않는게 좋고, 첫 시작이기 때문에 인덱스 0의 숫자에 해당하는 합계에서만 true가 됨
        if (nums[0] <= halfTotal) {
            memo[0][nums[0]] = true
        }

        for (idx in 1..nums.size-1) {
            for (total in 1..halfTotal) {
	            // 이전의 인덱스에서 해당 total이 참이였다면 지금도 참이 된다. || nums의 숫자와 total이 같으면 참이 된다.
                memo[idx][total] = memo[idx-1][total] || (nums[idx] == total)

				// nums의 숫자가 total 보다 크면 그 전의 인덱스에서 total-nums의 숫자에 해당하는 결과가 참이였는지를 보면 된다.
                if (total-nums[idx] >= 0) {
                    memo[idx][total] = memo[idx][total] || memo[idx-1][total-nums[idx]]
                }
            }
        }

        return memo[nums.size-1][halfTotal]
    }
}

4. 복잡도

시간 복잡도: O(N^2)
공간 복잡도: N^2