onenoughtone

Code Implementation

Partition Equal Subset Sum Implementation

Below is the implementation of the partition equal subset sum:

solution.js

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
/**
 * Determine if the array can be partitioned into two subsets with equal sum.
 * Dynamic Programming (2D) approach.
 *
 * @param {number[]} nums - Array of integers
 * @return {boolean} - True if the array can be partitioned, false otherwise
 */
function canPartition(nums) {
  // Calculate the total sum of the array
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
 
  // If the total sum is odd, return false
  if (totalSum % 2 !== 0) {
    return false;
  }
 
  const target = totalSum / 2;
  const n = nums.length;
 
  // Initialize DP array
  const dp = Array(n + 1).fill().map(() => Array(target + 1).fill(false));
 
  // Base cases
  dp[0][0] = true;
 
  // Fill DP array
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= target; j++) {
      // Exclude the current element
      dp[i][j] = dp[i - 1][j];
 
      // Include the current element if possible
      if (j >= nums[i - 1]) {
        dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
      }
    }
  }
 
  return dp[n][target];
}
 
/**
 * Determine if the array can be partitioned into two subsets with equal sum.
 * Dynamic Programming (1D) approach.
 *
 * @param {number[]} nums - Array of integers
 * @return {boolean} - True if the array can be partitioned, false otherwise
 */
function canPartitionOptimized(nums) {
  // Calculate the total sum of the array
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
 
  // If the total sum is odd, return false
  if (totalSum % 2 !== 0) {
    return false;
  }
 
  const target = totalSum / 2;
 
  // Initialize DP array
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
 
  // Fill DP array
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
 
  return dp[target];
}
 
// Test cases
console.log(canPartition([1, 5, 11, 5]));  // true
console.log(canPartition([1, 2, 3, 5]));  // false
 
console.log(canPartitionOptimized([1, 5, 11, 5]));  // true
console.log(canPartitionOptimized([1, 2, 3, 5]));  // false

Step-by-Step Explanation

Let's break down the implementation:

Calculate Total Sum: Calculate the total sum of the array to determine if it's possible to partition it into two equal subsets.
Check for Odd Sum: If the total sum is odd, it's impossible to partition the array into two equal subsets, so return false.
Set Target Sum: Set the target sum to half of the total sum, as we need to find a subset with this sum.
Initialize DP Array: Initialize a DP array to keep track of which sums are possible to achieve with the given numbers.
Fill DP Array: For each number in the array, update the DP array to reflect which sums are possible to achieve.

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Implement the partition equal subset sum solution in different programming languages.

Partition Equal Subset Sum Implementation

Below is the implementation of the partition equal subset sum in different programming languages. Select a language tab to view the corresponding code.

solution.js

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
/**
 * Determine if the array can be partitioned into two subsets with equal sum.
 * Dynamic Programming (2D) approach.
 *
 * @param {number[]} nums - Array of integers
 * @return {boolean} - True if the array can be partitioned, false otherwise
 */
function canPartition(nums) {
  // Calculate the total sum of the array
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
 
  // If the total sum is odd, return false
  if (totalSum % 2 !== 0) {
    return false;
  }
 
  const target = totalSum / 2;
  const n = nums.length;
 
  // Initialize DP array
  const dp = Array(n + 1).fill().map(() => Array(target + 1).fill(false));
 
  // Base cases
  dp[0][0] = true;
 
  // Fill DP array
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= target; j++) {
      // Exclude the current element
      dp[i][j] = dp[i - 1][j];
 
      // Include the current element if possible
      if (j >= nums[i - 1]) {
        dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
      }
    }
  }
 
  return dp[n][target];
}
 
/**
 * Determine if the array can be partitioned into two subsets with equal sum.
 * Dynamic Programming (1D) approach.
 *
 * @param {number[]} nums - Array of integers
 * @return {boolean} - True if the array can be partitioned, false otherwise
 */
function canPartitionOptimized(nums) {
  // Calculate the total sum of the array
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
 
  // If the total sum is odd, return false
  if (totalSum % 2 !== 0) {
    return false;
  }
 
  const target = totalSum / 2;
 
  // Initialize DP array
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
 
  // Fill DP array
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
 
  return dp[target];
}
 
// Test cases
console.log(canPartition([1, 5, 11, 5]));  // true
console.log(canPartition([1, 2, 3, 5]));  // false
 
console.log(canPartitionOptimized([1, 5, 11, 5]));  // true
console.log(canPartitionOptimized([1, 2, 3, 5]));  // false

Step-by-Step Explanation

1Calculate Total Sum

Calculate the total sum of the array to determine if it's possible to partition it into two equal subsets.

2Check for Odd Sum

If the total sum is odd, it's impossible to partition the array into two equal subsets, so return false.

3Set Target Sum

Set the target sum to half of the total sum, as we need to find a subset with this sum.

4Initialize DP Array

Initialize a DP array to keep track of which sums are possible to achieve with the given numbers.

5Fill DP Array

For each number in the array, update the DP array to reflect which sums are possible to achieve.

Language-Specific Notes

javascript

JavaScript's reduce() method is used to calculate the sum of all elements in the array.
The % operator is used to check if the total sum is odd or even.
Array.fill().map() is used to create a 2D array for the dynamic programming approach.
The || operator is used for logical OR operations in the DP state transitions.
The for...of loop is used to iterate through the array in the optimized approach.

python

Python's built-in sum() function is used to calculate the sum of all elements in the array.
The % operator is used to check if the total sum is odd or even.
List comprehension [[False] * (target + 1) for _ in range(n + 1)] is used to create a 2D array.
The or operator is used for logical OR operations in the DP state transitions.
The range() function with a step parameter is used to iterate through the array in reverse order.

java

Java uses a for-each loop to calculate the sum of all elements in the array.
The % operator is used to check if the total sum is odd or even.
Arrays are initialized with a specific size using new boolean[n + 1][target + 1].
The || operator is used for logical OR operations in the DP state transitions.
The for-each loop is used to iterate through the array in the optimized approach.

cpp

C++'s std::accumulate() function is used to calculate the sum of all elements in the array.
The % operator is used to check if the total sum is odd or even.
std::vector> is used to create a 2D vector with initialization.
The || operator is used for logical OR operations in the DP state transitions.
std::boolalpha is used to print boolean values as 'true' or 'false' instead of 1 or 0.

Key Takeaways

This problem is equivalent to finding a subset with a sum equal to half of the total sum.
If the total sum is odd, it's impossible to partition the array into two equal subsets.
Dynamic programming is an efficient approach to solve this problem, with either a 2D or 1D DP array.
The 1D DP approach optimizes the space complexity from O(n * target) to O(target).
When using a 1D DP array, it's important to iterate through the sums in reverse order to avoid using updated values in the same iteration.

Try It Yourself

Modify the code to implement an alternative approach and test it with the same examples.

Challenge:

Implement a function that solves the partition equal subset sum problem using a different approach than shown above.

Common Edge Cases

Empty Array

Handle the case where the array is empty (return true, as both subsets would be empty with a sum of 0).

nums = []

Single Element

Handle the case where the array has only one element (return false, as it's impossible to partition a single element into two equal subsets).

nums = [5]

All Zeros

Handle the case where all elements are zeros (return true, as both subsets would have a sum of 0).

nums = [0, 0, 0]

Solution Approach All Problems

Problem Solution Code

onenoughtone

Back to Home

onenoughtone

Back to Home

Partition Equal Subset Sum - Implementation

Code Implementation

Partition Equal Subset Sum Implementation

Below is the implementation of the partition equal subset sum:

solution.js

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
/**
 * Determine if the array can be partitioned into two subsets with equal sum.
 * Dynamic Programming (2D) approach.
 *
 * @param {number[]} nums - Array of integers
 * @return {boolean} - True if the array can be partitioned, false otherwise
 */
function canPartition(nums) {
  // Calculate the total sum of the array
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
 
  // If the total sum is odd, return false
  if (totalSum % 2 !== 0) {
    return false;
  }
 
  const target = totalSum / 2;
  const n = nums.length;
 
  // Initialize DP array
  const dp = Array(n + 1).fill().map(() => Array(target + 1).fill(false));
 
  // Base cases
  dp[0][0] = true;
 
  // Fill DP array
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= target; j++) {
      // Exclude the current element
      dp[i][j] = dp[i - 1][j];
 
      // Include the current element if possible
      if (j >= nums[i - 1]) {
        dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
      }
    }
  }
 
  return dp[n][target];
}
 
/**
 * Determine if the array can be partitioned into two subsets with equal sum.
 * Dynamic Programming (1D) approach.
 *
 * @param {number[]} nums - Array of integers
 * @return {boolean} - True if the array can be partitioned, false otherwise
 */
function canPartitionOptimized(nums) {
  // Calculate the total sum of the array
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
 
  // If the total sum is odd, return false
  if (totalSum % 2 !== 0) {
    return false;
  }
 
  const target = totalSum / 2;
 
  // Initialize DP array
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
 
  // Fill DP array
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
 
  return dp[target];
}
 
// Test cases
console.log(canPartition([1, 5, 11, 5]));  // true
console.log(canPartition([1, 2, 3, 5]));  // false
 
console.log(canPartitionOptimized([1, 5, 11, 5]));  // true
console.log(canPartitionOptimized([1, 2, 3, 5]));  // false

Step-by-Step Explanation

Let's break down the implementation:

Calculate Total Sum: Calculate the total sum of the array to determine if it's possible to partition it into two equal subsets.
Check for Odd Sum: If the total sum is odd, it's impossible to partition the array into two equal subsets, so return false.
Set Target Sum: Set the target sum to half of the total sum, as we need to find a subset with this sum.
Initialize DP Array: Initialize a DP array to keep track of which sums are possible to achieve with the given numbers.
Fill DP Array: For each number in the array, update the DP array to reflect which sums are possible to achieve.

Previous Next

String Problems

Palindrome Checker

Determine if a string reads the same forward and backward.

EasyString Manipulation

Message Encryption

Reverse a string to create a simple encryption system.

EasyString Manipulation

Word Puzzle Challenge

Check if two strings are anagrams of each other.

EasyString Manipulation

Learning Objective

Implement the partition equal subset sum solution in different programming languages.

Partition Equal Subset Sum Implementation

Below is the implementation of the partition equal subset sum in different programming languages. Select a language tab to view the corresponding code.

solution.js

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
/**
 * Determine if the array can be partitioned into two subsets with equal sum.
 * Dynamic Programming (2D) approach.
 *
 * @param {number[]} nums - Array of integers
 * @return {boolean} - True if the array can be partitioned, false otherwise
 */
function canPartition(nums) {
  // Calculate the total sum of the array
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
 
  // If the total sum is odd, return false
  if (totalSum % 2 !== 0) {
    return false;
  }
 
  const target = totalSum / 2;
  const n = nums.length;
 
  // Initialize DP array
  const dp = Array(n + 1).fill().map(() => Array(target + 1).fill(false));
 
  // Base cases
  dp[0][0] = true;
 
  // Fill DP array
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j <= target; j++) {
      // Exclude the current element
      dp[i][j] = dp[i - 1][j];
 
      // Include the current element if possible
      if (j >= nums[i - 1]) {
        dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
      }
    }
  }
 
  return dp[n][target];
}
 
/**
 * Determine if the array can be partitioned into two subsets with equal sum.
 * Dynamic Programming (1D) approach.
 *
 * @param {number[]} nums - Array of integers
 * @return {boolean} - True if the array can be partitioned, false otherwise
 */
function canPartitionOptimized(nums) {
  // Calculate the total sum of the array
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
 
  // If the total sum is odd, return false
  if (totalSum % 2 !== 0) {
    return false;
  }
 
  const target = totalSum / 2;
 
  // Initialize DP array
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
 
  // Fill DP array
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
 
  return dp[target];
}
 
// Test cases
console.log(canPartition([1, 5, 11, 5]));  // true
console.log(canPartition([1, 2, 3, 5]));  // false
 
console.log(canPartitionOptimized([1, 5, 11, 5]));  // true
console.log(canPartitionOptimized([1, 2, 3, 5]));  // false

Step-by-Step Explanation

1Calculate Total Sum

Calculate the total sum of the array to determine if it's possible to partition it into two equal subsets.

2Check for Odd Sum

If the total sum is odd, it's impossible to partition the array into two equal subsets, so return false.

3Set Target Sum

Set the target sum to half of the total sum, as we need to find a subset with this sum.

4Initialize DP Array

Initialize a DP array to keep track of which sums are possible to achieve with the given numbers.

5Fill DP Array

For each number in the array, update the DP array to reflect which sums are possible to achieve.

Language-Specific Notes

javascript

JavaScript's reduce() method is used to calculate the sum of all elements in the array.
The % operator is used to check if the total sum is odd or even.
Array.fill().map() is used to create a 2D array for the dynamic programming approach.
The || operator is used for logical OR operations in the DP state transitions.
The for...of loop is used to iterate through the array in the optimized approach.

python

Python's built-in sum() function is used to calculate the sum of all elements in the array.
The % operator is used to check if the total sum is odd or even.
List comprehension [[False] * (target + 1) for _ in range(n + 1)] is used to create a 2D array.
The or operator is used for logical OR operations in the DP state transitions.
The range() function with a step parameter is used to iterate through the array in reverse order.

java

Java uses a for-each loop to calculate the sum of all elements in the array.
The % operator is used to check if the total sum is odd or even.
Arrays are initialized with a specific size using new boolean[n + 1][target + 1].
The || operator is used for logical OR operations in the DP state transitions.
The for-each loop is used to iterate through the array in the optimized approach.

cpp

C++'s std::accumulate() function is used to calculate the sum of all elements in the array.
The % operator is used to check if the total sum is odd or even.
std::vector> is used to create a 2D vector with initialization.
The || operator is used for logical OR operations in the DP state transitions.
std::boolalpha is used to print boolean values as 'true' or 'false' instead of 1 or 0.

Key Takeaways

This problem is equivalent to finding a subset with a sum equal to half of the total sum.
If the total sum is odd, it's impossible to partition the array into two equal subsets.
Dynamic programming is an efficient approach to solve this problem, with either a 2D or 1D DP array.
The 1D DP approach optimizes the space complexity from O(n * target) to O(target).
When using a 1D DP array, it's important to iterate through the sums in reverse order to avoid using updated values in the same iteration.

Try It Yourself

Modify the code to implement an alternative approach and test it with the same examples.

Challenge:

Implement a function that solves the partition equal subset sum problem using a different approach than shown above.

Common Edge Cases

Empty Array

Handle the case where the array is empty (return true, as both subsets would be empty with a sum of 0).

nums = []

Single Element

Handle the case where the array has only one element (return false, as it's impossible to partition a single element into two equal subsets).

nums = [5]

All Zeros

Handle the case where all elements are zeros (return true, as both subsets would have a sum of 0).

nums = [0, 0, 0]

Solution Approach All Problems

Code Implementation

Partition Equal Subset Sum Implementation

Step-by-Step Explanation

String ProblemsShow All

Palindrome Checker

Message Encryption

Word Puzzle Challenge

Learning Objective

Partition Equal Subset Sum Implementation

Step-by-Step Explanation

1Calculate Total Sum

2Check for Odd Sum

3Set Target Sum

4Initialize DP Array

5Fill DP Array

Language-Specific Notes

javascript

python

java

cpp

Key Takeaways

Try It Yourself

Challenge:

Common Edge Cases

Empty Array

Single Element

All Zeros

Partition Equal Subset Sum - Implementation

Code Implementation

Partition Equal Subset Sum Implementation

Step-by-Step Explanation

String ProblemsShow All

Palindrome Checker

Message Encryption

Word Puzzle Challenge

Learning Objective

Partition Equal Subset Sum Implementation

Step-by-Step Explanation

1Calculate Total Sum

2Check for Odd Sum

3Set Target Sum

4Initialize DP Array

5Fill DP Array

Language-Specific Notes

javascript

python

java

cpp

Key Takeaways

Try It Yourself

Challenge:

Common Edge Cases

Empty Array

Single Element

All Zeros

String Problems

String Problems