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, otherwise return false.
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Input: nums = [1,2,5]
Output: false
1 <= nums.length <= 2001 <= nums[i] <= 100This is a 0/1 Knapsack problem in disguise!
total / 2Build a 2D DP table where dp[i][j] = true if we can achieve sum j using first i elements.
dp[i][j] = dp[i-1][j]dp[i][j] |= dp[i-1][j-nums[i-1]]Optimize space by using 1D array and processing right to left.
dp[sum] |= dp[sum - num]Try all possible partitions with memoization.
Use bitset to track all achievable sums efficiently.
| Approach | Time | Space | |----------|------|-------| | 2D DP | O(n × sum) | O(n × sum) | | 1D DP | O(n × sum) | O(sum) | | Backtracking + Memo | O(n × sum) | O(n × sum) | | BitSet | O(n × sum) | O(sum/64) |
This problem demonstrates:
1import java.util.*;
2
3class Solution {
4 // Solution 1: Dynamic Programming (2D)
5 public boolean canPartition(int[] nums) {
6 int total = 0;
7 for (int num : nums) {
8 total += num;
9 }
10
11 // If total is odd, can't partition equally
12 if (total % 2 != 0) {
13 return false;
14 }
15
16 int target = total / 2;
17 int n = nums.length;
18
19 // dp[i][j] = can we achieve sum j using first i elements
20 boolean[][] dp = new boolean[n + 1][target + 1];
21
22 // Base case: sum 0 is always achievable (empty subset)
23 for (int i = 0; i <= n; i++) {
24 dp[i][0] = true;
25 }
26
27 // Fill the DP table
28 for (int i = 1; i <= n; i++) {
29 for (int j = 0; j <= target; j++) {
30 // Don't take current element
31 dp[i][j] = dp[i - 1][j];
32
33 // Take current element (if possible)
34 if (j >= nums[i - 1]) {
35 dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
36 }
37 }
38 }
39
40 return dp[n][target];
41 }
42
43 // Solution 2: Dynamic Programming (1D Optimized)
44 public boolean canPartitionOptimized(int[] nums) {
45 int total = 0;
46 for (int num : nums) {
47 total += num;
48 }
49
50 // If total is odd, can't partition equally
51 if (total % 2 != 0) {
52 return false;
53 }
54
55 int target = total / 2;
56
57 // dp[j] = can we achieve sum j
58 boolean[] dp = new boolean[target + 1];
59 dp[0] = true;
60
61 // Process each number
62 for (int num : nums) {
63 // Process right to left to avoid using same element twice
64 for (int j = target; j >= num; j--) {
65 dp[j] = dp[j] || dp[j - num];
66 }
67 }
68
69 return dp[target];
70 }
71
72 // Solution 3: Backtracking with Memoization
73 public boolean canPartitionBacktrack(int[] nums) {
74 int total = 0;
75 for (int num : nums) {
76 total += num;
77 }
78
79 if (total % 2 != 0) {
80 return false;
81 }
82
83 int target = total / 2;
84 Map<String, Boolean> memo = new HashMap<>();
85 return backtrack(nums, 0, 0, target, memo);
86 }
87
88 private boolean backtrack(int[] nums, int index, int currentSum,
89 int target, Map<String, Boolean> memo) {
90 // Base cases
91 if (currentSum == target) {
92 return true;
93 }
94 if (currentSum > target || index >= nums.length) {
95 return false;
96 }
97
98 // Check memo
99 String key = index + "," + currentSum;
100 if (memo.containsKey(key)) {
101 return memo.get(key);
102 }
103
104 // Try taking current element or skipping it
105 boolean result = backtrack(nums, index + 1, currentSum + nums[index], target, memo) // Take
106 || backtrack(nums, index + 1, currentSum, target, memo); // Skip
107
108 memo.put(key, result);
109 return result;
110 }
111
112 // Solution 4: Set-based Approach
113 public boolean canPartitionSet(int[] nums) {
114 int total = 0;
115 for (int num : nums) {
116 total += num;
117 }
118
119 if (total % 2 != 0) {
120 return false;
121 }
122
123 int target = total / 2;
124
125 // Set of all achievable sums
126 Set<Integer> possibleSums = new HashSet<>();
127 possibleSums.add(0);
128
129 for (int num : nums) {
130 // Create new sums by adding current number to existing sums
131 Set<Integer> newSums = new HashSet<>();
132 for (int sum : possibleSums) {
133 int newSum = sum + num;
134 if (newSum == target) {
135 return true;
136 }
137 if (newSum < target) {
138 newSums.add(newSum);
139 }
140 }
141 possibleSums.addAll(newSums);
142 }
143
144 return possibleSums.contains(target);
145 }
146
147 // Solution 5: BitSet Optimization
148 public boolean canPartitionBitSet(int[] nums) {
149 int total = 0;
150 for (int num : nums) {
151 total += num;
152 }
153
154 if (total % 2 != 0) {
155 return false;
156 }
157
158 int target = total / 2;
159
160 // Use BitSet to track achievable sums
161 BitSet bits = new BitSet(target + 1);
162 bits.set(0); // Sum 0 is achievable
163
164 for (int num : nums) {
165 // Create new bitset shifted by num positions
166 BitSet shifted = (BitSet) bits.clone();
167 for (int i = 0; i <= target - num; i++) {
168 if (bits.get(i)) {
169 shifted.set(i + num);
170 }
171 }
172 bits.or(shifted);
173 }
174
175 return bits.get(target);
176 }
177}
178