-
Notifications
You must be signed in to change notification settings - Fork 22
Expand file tree
/
Copy path416.partition-equal-subset-sum.cpp
More file actions
79 lines (71 loc) · 1.92 KB
/
416.partition-equal-subset-sum.cpp
File metadata and controls
79 lines (71 loc) · 1.92 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// Tag: Array, Dynamic Programming
// Time: O(N^2)
// Space: O(N)
// Ref: -
// Note: -
// Video: https://youtu.be/5uRXSdLOz1o
// 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
//
//
class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = accumulate(nums.begin(), nums.end(), 0);
if (total % 2 == 1) {
return false;
}
int n = nums.size();
int target = total / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = target; j >= nums[i - 1]; j--) {
dp[j] = dp[j] || dp[j - nums[i - 1]];
}
}
return dp[target];
}
};
class Solution {
public:
bool canPartition(vector<int>& nums) {
int total = accumulate(nums.begin(), nums.end(), 0);
if (total % 2 == 1) {
return false;
}
int n = nums.size();
int k = total / 2;
vector<vector<bool>> dp(n + 1, vector<bool>(k + 1, false));
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
if (nums[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][k];
}
};