[LeetCode] 698. Partition to K Equal Sum Subsets

문제 출처: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

Partition to K Equal Sum Subsets - LeetCode

---

문제

정수 배열 nums와 정수 k가 주어지면, 합이 동일한 k개의 비어있지 않는 부분집합을 만들 수 있다면 true를 반환하라.

예제

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true

Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Input: nums = [1,2,3,4], k = 3
Output: false

---

풀이

주어진 nums를 k개로 분할할 때 각 부분 집합의 합이 몇이 되어야 하는지 구해야 합니다. 이를 위해서 nums의 합을 k로 나누어 볼 수 있습니다.

 

만약 나눈 나머지가 0이 아니라면 애초에 동일한 합을 갖는 k개의 부분 집합으로 나누는 게 불가능하기 때문에 false를 바로 반환하고, 그렇지 않다면 몫만큼의 합을 갖는 부분 집합들로 나눌 수 있는지 체크해야 합니다.

 

이를 기반으로 아래와 같은 코드 틀을 만들어 볼 수 있습니다.

var canPartitionSubSets = function(nums, k) {
    const total = nums.reduce((acc, val) => acc + val, 0);
    if (total % k) { return false; }
    const target = total / k;
    
    // k개의 부분 집합을 만들 수 있는지 체크 과정
    for (let i = 0; i < k; i++) {
    	// 합이 target인 부분집합을 만들 수 있는지 체크하는 findSubset()이 있다고 가정
    	if (!findSubset()) {
        	return false;
        }
    }
    
    return true;
}

findSubset()에 대해서 생각해봅시다. 단순히 특정 합을 만드는 부분 집합 하나를 찾는 한다면, 아래와 같이 재귀적인 방식으로 찾을 수 있습니다.

var findSubset = function(arr, idx, target) {
    if (target == 0) { return true; }
    for (let i = idx; i < arr.length; i++) {
    	if (target - arr[i] < 0) { continue; }
        if (findSubset(arr, target - arr[i], idx+1)) {
            return true;
        }
    }
    return false;
}

다만, 현재 문제에서 요구하는 바는 k개의 부분 집합을 만드는 것을 원하기 때문에 어떤 원소들이 선택할 수 있는지에 대한 정보가 추가적으로 필요하고 이를 바탕으로 다음과 같이 코드를 수정할 수 있습니다.

var findSubset = function(arr, used, idx, target) {
    if (target == 0) { return true; }
    for (let i = idx; i < arr.length; i++) {
    	if (used[i] || target - arr[i] < 0) { continue; }
        
        used[i] = true;
        if (findSubset(arr, target - arr[i], idx+1)) {
            return true;
        }
        used[i] = false;
    }
    return false;
}

아직 고려해야 할 점이 한 가지 남아있습니다. 다음의 예를 생각해봅시다.

 

nums = [1,1,1,1,2,2,2,2], k = 4 라면, 한 집합 당, 합이 3으로 만들어져야 하고, 앞에서부터 순서대로 (1,1,1), (1,2)로 묶이게 됩니다. 결국 남는 숫자가 2 뿐이기 때문에 3을 만들 수 없어 false를 출력하게 됩니다.

 

이를 해결하기 위해 탐욕적(Greedy)인 방식으로 숫자를 선택하는 방법을 생각해볼 수 있습니다. 큰 숫자를 우선적으로 선택하게 되면 작은 숫자들끼리 묶여 목표 값을 만드는 케이스를 가장 나중에 볼 수 있기 때문입니다. 또한 작은 숫자는 다양한 조합이 가능하기 때문에 꼭 그 숫자가 필요한 순간에 사용되도록 하기 위함도 있습니다.

 

이러한 탐욕적 방식을 사용하면, findSubset()의 추가적인 변경 없이 메인 함수를 다음과 같이 수정하는 것으로 문제의 답을 찾을 수 있습니다.

var canPartitionSubSets = function(nums, k) {
    const total = nums.reduce((acc, val) => acc + val, 0);
    if (total % k) { return false; }
    const target = total / k;
    
    nums = nums.sort((a, b) => b - a);
    const used = new Array(nums.length).fill(false);
    
    for (let i = 0; i < k; i++) {
    	if (!findSubset(nums, used, 0, target)) {
        	return false;
        }
    }
    
    return true;
}

시간 복잡도를 계산하면,

• 정렬: $O(nlogn)$
• findSubset(): $O(2^n)$
  • n개의 원소에 대해 선택하는 케이스와 그렇지 않은 케이스를 살펴보기 때문

• k번의 findSubset() 호출: $O(k*2^n)$

 

종합하면, $O(nlogn + k*2^n)$인데, $O(k*2^n)$으로 표현할 수 있습니다.

 

Github: 698.js

GitHub - opwe37/Algorithm-Study