{"id":10220,"date":"2025-10-03T13:53:26","date_gmt":"2025-10-03T08:23:26","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=10220"},"modified":"2025-10-03T14:47:41","modified_gmt":"2025-10-03T09:17:41","slug":"partition-equal-subset-sum","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/partition-equal-subset-sum\/","title":{"rendered":"Partition Equal Subset Sum"},"content":{"rendered":"\n<!-- PrismJS for Syntax Highlighting -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\" rel=\"stylesheet\">\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style>\n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #030302;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2 {\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n\n.wp_blog_explanation code {\n  background: #fef9f4;   \/* light bg instead of dark blue *\/\n  color: #E58C32;        \/* brand orange *\/\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n  font-weight: 600;      \/* optional, makes it pop *\/\n}\n\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0, 0, 0, 0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n\n\/* Dark mode variables *\/\n.wp_blog_theme.dark-mode {\n  --light-bg: #121212;\n  --text-dark: #f5f5f5;\n  --shadow: 0 4px 12px rgba(255, 255, 255, 0.08);\n  --code-bg: #1e1e1e;\n  --code-text: #c5f0ff;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_explanation {\n  background: #1e1e1e;\n}\n\n\/* Dark mode code highlight *\/\n.wp_blog_theme.dark-mode .wp_blog_explanation code {\n  background: #333;\n  color: #ffd27f;\n}\n\n.wp_blog_theme {\n  position: relative; \/* makes it the reference for absolute children *\/\n}\n\n.wp_blog_toggle-btn {\n  position: absolute;\n  top: 1rem;\n  right: 1rem;\n  z-index: 9999;\n  padding: 0.5rem 0.8rem;\n  border-radius: 10%;\n  background: var(--primary);\n  color: white;\n  font-weight: bold;\n  cursor: pointer;\n  border: none;\n  box-shadow: var(--shadow);\n  transition: background 0.3s, transform 0.2s;\n}\n\n.wp_blog_toggle-btn:hover {\n  background: #cc772e;\n}\n\n.wp_blog_theme.dark-mode .wp_blog_code-tabs-container {\n  background: #1e1e1e;\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\">\n  <button id=\"blogNotesThemeToggle\" class=\"wp_blog_toggle-btn\">\ud83c\udf19<\/button>\n  <h1 class=\"wp_blog_main-heading\"><\/h1>\n\n  <div class=\"wp_blog_explanation\">\n    <h2>Problem Statement:<\/h2>\n   <p>\n    Given an integer array <code>nums<\/code>, return <code>true<\/code> <i>if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or <code>false<\/code> otherwise<\/i>.\n   <\/p>\n    <h3>Example 1:<\/h2>\n    <p><strong>Input:<\/strong> nums = [1,5,11,5]<\/p>\n    <p><strong>Output:<\/strong> true<\/p>\n    <p><strong>Explanation:<\/strong> The array can be partitioned as [1, 5, 5] and [11].<\/p>\n\n    <h3>Example 2:<\/h2>\n    <p><strong>Input:<\/strong> nums = [1, 2, 3, 5]<\/p>\n    <p><strong>Output:<\/strong> false<\/p>\n    <p><strong>Explanation:<\/strong> The array can be partitioned as [1, 5, 5] and [11].<\/p>\n\n    <h3>Constraints<\/h3>\n    <ul>\n       <li><code>1 <= nums.length <= 200<\/code><\/li>\n        <li><code>1 <= nums[i] <= 100<\/code><\/li>\n    <\/ul>\n    \n<h2>Approach:<\/h2>\n<ul>\n    <li><strong>Do calculate the total sum of the array.<\/strong>\n    <ul>\n        <li>If the <code>sum<\/code> is odd, immediately return <code>false<\/code> because it cannot be divided into two equal subsets.<\/li>\n    <\/ul>\n    <\/li>\n\n    <li><strong>Do divide the total sum by 2.<\/strong>\n    <ul>\n        <li>This becomes the target sum <code>sum<\/code> we need to achieve from a subset of the array.<\/li>\n    <\/ul>\n    <\/li>\n    \n    <li><strong>Do create a memoization table (<code>dp<\/code>).<\/strong>\n    <ul>\n        <li><code>dp[remS][start]<\/code> will store whether it is possible to form the remaining sum <code>remS<\/code> starting from index <code>start<\/code>.<\/li>\n    <\/ul>\n    <\/li>\n\n    <li><strong>Do define a recursive function <code>fn(remS, start)<\/code>:<\/strong>\n    <ul>\n        <li>If <code>remS == 0<\/code>, return <code>true<\/code> (subset found).<\/li>\n        <li>If <code>remS < 0<\/code>, return <code>false<\/code> (overshoot).<\/li>\n        <li>If already computed in <code>dp<\/code>, return the stored result.<\/li>\n    <\/ul>\n    <\/li>\n\n    <li><strong>Do iterate over all elements from <code>start<\/code> to <code>end<\/code>:<\/strong>\n    <ul>\n        <li>For each element, recursively check if choosing it <code>(remS - arr[i])<\/code> allows reaching the target.<\/li>\n        <li>If any path returns <code>true<\/code>, store <code>true<\/code> in <code>dp<\/code> and return it.<\/li>\n    <\/ul>\n    <\/li>\n\n    <li><strong>Do return <code>false<\/code> if no subset works from this position.<\/strong>\n    <ul>\n        <li>Save result in <code>dp[remS][start]<\/code>.<\/li>\n    <\/ul>\n    <\/li>\n\n    <li><strong>Do call <code>fn(sum, 0)<\/code> at the start.<\/strong>\n    <ul>\n        <li>This checks if we can form half of the total sum using elements from the beginning.<\/li>\n    <\/ul>\n    \n    <\/li>\n<\/ul>\n\n    <h2>Time & Space Complexity:<\/h2>\n    <p><strong>Time Complexity:<\/strong> <code>O(n*sum)<\/code><\/p>\n    <p><strong>Space Complexity:<\/strong> <code>O(n*sum)<\/code><\/p>\n\n <h2>Dry Run<\/h2>\n<div style=\"background: var(--light-bg); border-left: 4px solid var(--primary); padding: 1rem; border-radius: var(--tab-radius); margin: 1rem 0; color: var(--text-dark);\">\n  <p><strong>Input:<\/strong> <code>arr = [1, 5, 11, 5]<\/code><\/p>\n  <pre style=\"white-space: pre-wrap; background: var(--code-bg); padding: 1rem; border-radius: 8px; overflow-x: auto; color: var(--code-text);\">\nStep 0: Start canPartition([1, 5, 11, 5])\n sum = 1 + 5 + 11 + 5 = 22\n sum % 2 == 0 \u2192 target = sum \/ 2 = 11\n\n dp table: rows 0..11, cols 0..3 (all undefined)\n\nCall fn(remS = 11, start = 0)\n\nfn(11, 0):\n - remS != 0 and > 0\n - dp[11][0] undefined\n - Try i from 0 to 3\n\n i = 0 \u2192 use arr[0] = 1 \u2192 call fn(10, 1)\n\n   fn(10, 1):\n   - dp[10][1] undefined\n   - Try i = 1..3\n\n    i = 1 \u2192 use arr[1] = 5 \u2192 call fn(5, 2)\n\n      fn(5, 2):\n      - dp[5][2] undefined\n      - Try i = 2..3\n\n       i = 2 \u2192 use arr[2] = 11 \u2192 call fn(-6, 3)\n         fn(-6,3): remS < 0 \u2192 return false\n\n       i = 3 \u2192 use arr[3] = 5 \u2192 call fn(0, 4)\n         fn(0,4): remS == 0 \u2192 return true\n\n      fn(5,2): found true (from i=3)\n      \u2192 dp[5][2] = true\n      \u2192 return true\n\n    fn(10,1): fn(5,2) returned true\n    \u2192 dp[10][1] = true\n    \u2192 return true\n\n fn(11,0): fn(10,1) returned true\n \u2192 dp[11][0] = true\n \u2192 return true\n\nResult: fn(11,0) = true \u2192 canPartition returns true\n\nSome dp entries set during recursion:\n - dp[5][2]  = true\n - dp[10][1] = true\n - dp[11][0] = true\n\nStep End:\nReturn value = true  (example partition: [1,5,5] and [11])\n  <\/pre>\n\n  <p><strong>Output:<\/strong> <code>true<\/code><\/p>\n<\/div>\n\n\n\n        <!-- <h2>Visualisation:<\/h2>\n        <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/09\/Screenshot-2025-09-30-at-3.00.03\u202fPM.png\" alt=\"Stocks\" \/>\n    -->\n<\/div>\n\n\n  <div class=\"wp_blog_code-tabs-container\">\n    <div class=\"wp_blog_code-tabs-header\">\n      <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n      <pre><code class=\"language-javascript\">\nvar canPartition = function(arr) {\n    let sum = arr.reduce((acc, curr) => acc + curr, 0);\n    \/\/ if my total sum is odd, I can never reach 2 subset with equal sum\n    if(sum % 2) return false;\n    sum = sum \/ 2;\n\n    let dp = Array.from({ length: sum + 1}, () => Array(arr.length).fill(undefined))\n\n    let fn = (remS, start) => {\n        if(remS == 0) return true;\n        if(remS < 0) return false;\n\n        if(dp[remS][start] != undefined) return dp[remS][start];\n\n        for(let i=start; i < arr.length; i++){\n            if(fn(remS - arr[i], i + 1)) {\n                return dp[remS][start] = true;\n            }\n        }\n        return dp[remS][start] = false;\n    }\n\n    return fn(sum, 0);\n};\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n      <pre><code class=\"language-python\">\nfrom functools import lru_cache\nfrom typing import List\n\ndef canPartition(arr: List[int]) -> bool:\n    total = sum(arr)\n    if total % 2 != 0:\n        return False\n    target = total \/\/ 2\n    n = len(arr)\n\n    from functools import lru_cache\n    @lru_cache(None)\n    def dfs(rem, start):\n        if rem == 0:\n            return True\n        if rem < 0:\n            return False\n        for i in range(start, n):\n            if dfs(rem - arr[i], i + 1):\n                return True\n        return False\n\n    return dfs(target, 0)\n      <\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n      <pre><code class=\"language-java\">\nimport java.util.Arrays;\n\npublic class Solution {\n    private Integer[][] dp;\n    private int[] arr;\n\n    public boolean canPartition(int[] nums) {\n        arr = nums;\n        int total = 0;\n        for (int x : arr) total += x;\n        if (total % 2 != 0) return false;\n        int target = total \/ 2;\n        dp = new Integer[target + 1][arr.length];\n        return dfs(target, 0);\n    }\n\n    private boolean dfs(int rem, int start) {\n        if (rem == 0) return true;\n        if (rem < 0) return false;\n        if (dp[rem][start] != null) return dp[rem][start];\n        for (int i = start; i < arr.length; i++) {\n            if (dfs(rem - arr[i], i + 1)) {\n                dp[rem][start] = 1;\n                return true;\n            }\n        }\n        dp[rem][start] = 0;\n        return false;\n    }\n}\n<\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n      <pre><code class=\"language-cpp\">\n#include &lt;bits\/stdc++.h&gt;     \nusing namespace std;\n\nbool dfs(int rem, int start, const vector<int>& arr, vector<vector<int>>& dp) {\n    if (rem == 0) return true;\n    if (rem < 0) return false;\n    if (dp[rem][start] != -1) return dp[rem][start];\n\n    int n = arr.size();\n    for (int i = start; i < n; ++i) {\n        if (dfs(rem - arr[i], i + 1, arr, dp)) {\n            dp[rem][start] = 1;\n            return true;\n        }\n    }\n    dp[rem][start] = 0;\n    return false;\n}\n\nbool canPartition(vector<int> arr) {\n    int total = accumulate(arr.begin(), arr.end(), 0);\n    if (total % 2 != 0) return false;\n    int target = total \/ 2;\n    int n = arr.size();\n    vector<vector<int>> dp(target + 1, vector<int>(n, -1));\n    return dfs(target, 0, arr, dp);\n}\n<\/code><\/pre>\n    <\/div>\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n      <pre><code class=\"language-c\">\n#include &lt;stdio.h&gt;\n#include &lt;stdlib.h&gt;\n\nint n;\nint *arr;\nint **dp; \/\/ dp[rem][start], -1 unknown, 0 false, 1 true\nint dfs(int rem, int start) {\n    if (rem == 0) return 1;\n    if (rem < 0) return 0;\n    if (dp[rem][start] != -1) return dp[rem][start];\n    for (int i = start; i < n; ++i) {\n        if (dfs(rem - arr[i], i + 1)) {\n            dp[rem][start] = 1;\n            return 1;\n        }\n    }\n    dp[rem][start] = 0;\n    return 0;\n}\nint canPartition(int *input, int length) {\n    arr = input;\n    n = length;\n    int total = 0;\n    for (int i = 0; i < n; ++i) total += arr[i];\n    if (total % 2 != 0) return 0;\n    int target = total \/ 2;\n\n    \/\/ allocate dp: (target+1) x n\n    dp = (int**) malloc((target + 1) * sizeof(int*));\n    for (int i = 0; i <= target; ++i) {\n        dp[i] = (int*) malloc(n * sizeof(int));\n        for (int j = 0; j < n; ++j) dp[i][j] = -1;\n    }\n    int res = dfs(target, 0);\n    for (int i = 0; i <= target; ++i) free(dp[i]);\n    free(dp);\n    return res;\n}\n <\/code><\/pre>\n    <\/div>\n\n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n      <pre><code class=\"language-csharp\">\nusing System;\nusing System.Linq;\n\nclass Solution {\n    static int[][] dp;\n    static int[] arr;\n    static bool Dfs(int rem, int start) {\n        if (rem == 0) return true;\n        if (rem < 0) return false;\n        if (dp[rem][start] != int.MinValue) return dp[rem][start] == 1;\n\n        for (int i = start; i < arr.Length; i++) {\n            if (Dfs(rem - arr[i], i + 1)) {\n                dp[rem][start] = 1;\n                return true;\n            }\n        }\n        dp[rem][start] = 0;\n        return false;\n    }\n    public static bool CanPartition(int[] input) {\n        arr = input;\n        int total = arr.Sum();\n        if (total % 2 != 0) return false;\n        int target = total \/ 2;\n        dp = new int[target + 1][];\n        for (int i = 0; i <= target; i++) {\n            dp[i] = Enumerable.Repeat(int.MinValue, arr.Length).ToArray();\n        }\n        return Dfs(target, 0);\n    }\n}\n      <\/code><\/pre>\n    <\/div>\n  <\/div>\n<\/div>\n\n<script>\ndocument.addEventListener(\"DOMContentLoaded\", () => {\n  const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n  const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n  buttons.forEach((button) => {\n    button.addEventListener(\"click\", () => {\n      const lang = button.getAttribute(\"data-lang\");\n\n      buttons.forEach((btn) => btn.classList.remove(\"active\"));\n      contents.forEach((content) => content.classList.remove(\"active\"));\n\n      button.classList.add(\"active\");\n      document\n        .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n        .classList.add(\"active\");\n    });\n  });\n\n  const themeToggle = document.getElementById(\"blogNotesThemeToggle\");\n  const themeContainer = document.querySelector(\".wp_blog_theme\");\n\n  themeToggle.addEventListener(\"click\", () => {\n    themeContainer.classList.toggle(\"dark-mode\");\n    themeToggle.textContent =\n      themeContainer.classList.contains(\"dark-mode\") ? \"\u2600\ufe0f\" : \"\ud83c\udf19\";\n  });\n});\n<\/script>\n`\n","protected":false},"excerpt":{"rendered":"<p>\ud83c\udf19 Problem Statement: 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<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[210,322,176,175,211,811,810,174,172,173],"tags":[],"class_list":{"0":"post-10220","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-algorithms","7":"category-algorithms-and-data-structures","8":"category-csharp","9":"category-cplusplus","10":"category-data-structures","11":"category-data-structures-and-algorithms","12":"category-dsa","13":"category-java","14":"category-javascript","15":"category-python"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10220","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=10220"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10220\/revisions"}],"predecessor-version":[{"id":10221,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10220\/revisions\/10221"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=10220"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=10220"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=10220"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}