416. Partition Equal Subset Sum
Tags:
Medium
Skills:
DP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Đề bài yêu cầu kiểm tra có thể chia mảng số nguyên nums thành hai tập con có tổng bằng nhau hay không.
Approach
Solution
1function canPartition(nums: number[]): boolean {
2 const total_sum = nums.reduce((acc, cur) => acc + cur, 0);
3
4 if(total_sum % 2 !== 0) return false;
5
6 const target = total_sum / 2;
7 const dp: boolean[] = Array(target + 1).fill(false);
8 dp[0] = true;
9
10 for(const num of nums) {
11 for(let j = target; j >= num; --j) {
12 dp[j] = dp[j] || dp[j - num]
13 }
14 }
15
16 return dp[target]
17};