698. Partition to K Equal Sum Subsets / TypeScript

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

 

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Example 2:

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

 

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

 

 

풀이

function canPartitionKSubsets(nums: number[], k: number): boolean {
	const dp: number[] = new Array(1 << nums.length).fill(-1);
	let target = 0;
	for (const n of nums) {
		target += n;
	}
	if (target % k !== 0) {
		return false;
	}
	target /= k;
	dp[0] = 0;
	for (let i = 0; i < dp.length - 1; i++) {
		if (dp[i] === -1) {
			continue;
		}
		const curSum = dp[i];
		for (let j = 0; j < nums.length; j++) {
			const cand = nums[j];
			if ((i & (1 << j)) === 0 && curSum + cand <= target) {
				dp[i | (1 << j)] = (curSum + cand) % target;
			}
		}
		if (dp[dp.length - 1] === 0) {
			return true;
		}
	}
	return false;
}

 

주어진 배열 nums를 k개의 부분집합으로 나눌 수 있는지 여부를 확인하는 함수

 

예시

const nums = [4, 3, 2, 3, 5, 2, 1];
const k = 4;

 

1. 합 계산

먼저 배열 nums의 합을 구함

let target = 0;
for (const n of nums) {
    target += n;
}
// target = 4 + 3 + 2 + 3 + 5 + 2 + 1 = 20

2. 나눌 수 있는지 확인

target이 k로 나누어 떨어지는지 확인

 

if (target % k !== 0) {
    return false;
}
// target = 20, k = 4
// 20 % 4 === 0, 나누어 떨어지므로 계속 진행
target /= k;
// target = 20 / 4 = 5
// 각 부분집합의 합은 5가 되어야 함

 

3. 동적 배열 초기화

dp 배열을 초기화하고 dp[0]을 0으로 설정

const dp: number[] = new Array(1 << nums.length).fill(-1);
dp[0] = 0;
// nums.length = 7
// 1 << 7 = 2^7 = 128
// dp 배열의 크기는 128이고, 모두 -1로 초기화. 빈 집합의 합은 0으로 설정.

 

 

비트마스크와 DP 배열

1. 비트마스크 설명:
   • 각 비트마스크는 배열의 각 요소가 포함되었는지를 나타냄.
   • 예를 들어, 비트마스크 0000110은 배열의 2번째와 3번째 요소가 포함된 부분집합을 나타냄.
2. DP 배열의 의미:
   • dp[mask]는 비트마스크 mask로 표현된 부분집합이 현재 부분집합의 합이 목표 합(target)에 대한 나머지를 저장.
   • dp[0] = 0은 빈 부분집합의 합이 0이라는 의미.

 

4. 비트마스크를 사용한 부분집합 탐색

모든 가능한 부분집합을 탐색하면서 dp 배열을 업데이트

 

for (let i = 0; i < dp.length - 1; i++) {
    if (dp[i] === -1) {
        continue;
    }
    const curSum = dp[i];
    for (let j = 0; j < nums.length; j++) {
        const cand = nums[j];
        if ((i & (1 << j)) === 0 && curSum + cand <= target) {
            dp[i | (1 << j)] = (curSum + cand) % target;
        }
    }
    if (dp[dp.length - 1] === 0) {
        return true;
    }
}
return false;

 

(i & (1 << j)) === 0 설명

비트마스크와 비트 연산

• 비트마스크:
  • 비트마스크는 배열의 각 요소를 포함 여부를 나타내는 방법으로, 이진수의 비트를 사용하여 부분집합을 표현
  • 비트마스크 i에서 j번째 비트가 1이면, 배열의 j번째 요소가 포함된 상태를 나타냄.
• 비트 연산:
  • AND 연산 (&): 두 비트가 모두 1일 때만 1이 되는 연산.
  • OR 연산 (|): 두 비트 중 하나라도 1이면 1이 되는 연산.
  • Shift 연산 (<<): 비트를 왼쪽으로 이동시키는 연산
• 1 << j:
  • 이 표현식은 1을 왼쪽으로 j비트 이동시킴.
  • 예를 들어, j = 3이면 1 << 3은 이진수 00001000. 즉, 8.
  • 이는 j번째 비트가 1인 비트마스크를 생성.
• i & (1 << j):
  • 비트마스크 i와 1 << j의 AND 연산을 수행.
  • i에서 j번째 비트가 1이면, i & (1 << j)는 1 << j와 같은 값
  • i에서 j번째 비트가 0이면, i & (1 << j)는 0.
• (i & (1 << j)) === 0:
  • 이 표현식은 i에서 j번째 비트가 0인지 확인.
  • 즉, 현재 상태 i에서 j번째 요소가 포함되어 있지 않다는 의미

예시 1: 요소가 포함 된  경우

• i = 5 (이진수 0000101)
• j = 2 (비트 2를 검사)

1. 1 << 2는 이진수 0000100입니다. 즉, 4.
2. i & (1 << 2)는 0000101 & 0000100으로 0000100, 즉 4.
3. 4 !== 0, 따라서 i에서 j번째 비트는 1입니다. 즉, i = 5에서는 j번째 요소가 포함되어 있음

예시 2: 요소가 포함되지 않은 경우

• i = 7 (이진수 0000111)
• j = 3 (비트 3를 검사)

1. 1 << 3은 이진수 0001000입니다. 즉, 8입니다.
2. i & (1 << 3)는 0000111 & 0001000으로 0000000, 즉 0입니다.
3. 0 === 0, 따라서 i에서 j번째 비트는 0입니다. 즉, i = 7에서는 j번째 요소가 포함되어 있지 않음

 

예시: i = 0 (빈 부분집합)

1. dp[0] = 0 (빈 부분집합의 합은 0)

요소들을 하나씩 추가합니다:

• 요소 4를 추가하면: dp[1] = 4 (이진수 0000001)
• 요소 3을 추가하면: dp[2] = 3 (이진수 0000010)
• 요소 2를 추가하면: dp[4] = 2 (이진수 0000100)
• 요소 3을 추가하면: dp[8] = 3 (이진수 0001000)
• 요소 5를 추가하면: dp[16] = 5 (이진수 0010000)
• 요소 2를 추가하면: dp[32] = 2 (이진수 0100000)
• 요소 1을 추가하면: dp[64] = 1 (이진수 1000000)

예시: i = 1 (4 포함된 부분집합)

이제 dp[1]에서 시작하여 다른 요소들을 추가합니다:

1. dp[1] = 4

• 요소 3를 추가하면: dp[3] = (4 + 3) % 5 = 2 (이진수 0000011)
• 요소 2를 추가하면: dp[5] = (4 + 2) % 5 = 1 (이진수 0000101)
• 요소 3를 추가하면: dp[9] = (4 + 3) % 5 = 2 (이진수 0001001)
• 요소 5를 추가하면: dp[17] = (4 + 5) % 5 = 4 (이진수 0010001)
• 요소 2를 추가하면: dp[33] = (4 + 2) % 5 = 1 (이진수 0100001)
• 요소 1을 추가하면: dp[65] = (4 + 1) % 5 = 0 (이진수 1000001)

예시: i = 17 (4와 5 포함된 부분집합)

1. dp[17] = 4

• 요소 3를 추가하면: dp[19] = (4 + 3) % 5 = 2 (이진수 0010011)
• 요소 2를 추가하면: dp[21] = (4 + 2) % 5 = 1 (이진수 0010101)
• 요소 3를 추가하면: dp[25] = (4 + 3) % 5 = 2 (이진수 0011001)
• 요소 2를 추가하면: dp[49] = (4 + 2) % 5 = 1 (이진수 0110001)
• 요소 1을 추가하면: dp[81] = (4 + 1) % 5 = 0 (이진수 1010001)

 

 

최종 상태 dp[127] (이진수 1111111)이 0이면, nums 배열을 k개의 부분집합으로 나눌 수 있음을 의미

 

최종 상태 dp[127] 설명

1. 비트마스크 127:
   • 이진수로 1111111은 모든 요소가 포함된 집합을 나타냄. 즉, nums 배열의 모든 요소를 포함하는 부분집합.
   • 127은 2^7 - 1로, 7개의 요소가 모두 포함된 상태를 나타냄.
2. dp[127]의 값:
   • dp[127]이 0이라는 것은, 모든 요소를 포함한 부분집합의 합이 목표 합(target)으로 나누었을 때 나머지가 0이라는 의미.
   • 즉, 모든 요소를 사용하여 target의 배수로 나눌 수 있다는 것을 의미

왜 dp[127]이 0이면 가능한가?

1. 부분집합 합의 나머지:
   • dp 배열의 각 상태는 부분집합의 현재 합이 target으로 나눈 나머지를 저장.
   • 예를 들어, dp[17] = 4는 비트마스크 17 (즉, 0010001)으로 나타나는 부분집합의 합이 4라는 것을 의미합니다.
2. 부분집합의 정확성:
   • 최종 상태 dp[127]이 0이라는 것은 모든 요소를 포함한 부분집합의 합이 target의 배수라는 것.
   • 이는 전체 배열을 정확히 k개의 부분집합으로 나눌 수 있다는 것을 의미.
3. 전체 배열을 k개의 부분집합으로 나누는 방법:
   • dp[127]이 0이면, 전체 배열을 k개의 부분집합으로 나눌 수 있는 한 가지 방법이 있다는 것을 의미
   • 이는 비트마스크를 통해 모든 가능한 부분집합을 고려했을 때, 목표 합을 만족할 수 있는 부분집합 구성이 가능함을 나타냄