{"id":9361,"date":"2025-08-15T18:10:45","date_gmt":"2025-08-15T12:40:45","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=9361"},"modified":"2025-10-15T16:19:44","modified_gmt":"2025-10-15T10:49:44","slug":"subset-ii","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/subset-ii\/","title":{"rendered":"Subset II"},"content":{"rendered":"\n<!-- Evaluate Reverse Polish Notation 10-->\n<link\n    href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\"\n    rel=\"stylesheet\"\n\/>\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>Given an integer array nums that may contain duplicates, return all possible subsets (the power set).<\/p> \n    \n    <p>\n        The solution set must not contain duplicate subsets. Return the solution in any order.\n    <\/p>\n    <p><strong>Example 1:<\/strong><\/p>\n    <p><strong>Input:<\/strong>nums = [1,2,2]<\/p>\n    <p><strong>Output:<\/strong><code> [[],[1],[1,2],[1,2,2],[2],[2,2]]<\/code><\/p>\n\n    <p><strong>Example 2:<\/strong><\/p>\n    <p><strong>Input:<\/strong> nums = [0]<\/p>\n    <p><strong>Output:<\/strong><code>[[],[0]]<\/code><\/p>\n\n\n    <h2>Constraints:<\/h2>\n    <ul>\n        <li><code>1 <= nums.length <= 10<\/code><\/li>\n        <li><code>-10 <= nums[i] <= 10<\/code><\/li>\n    <\/ul>\n\n    <h2>Approach:<\/h2>\n    <ul>\n        <li><strong>Sort the array<\/strong> to bring duplicates together.<\/li>\n        <li>Use <strong>backtracking<\/strong> to explore all possible <code>subsets<\/code>.<\/li>\n        <li>At each recursion step:\n            <ul>\n                <li>Add the current subset (path) to the <code>result<\/code>.<\/li>\n                <li>Loop through remaining elements starting from <strong>start<\/strong>.<\/li>\n                <li><strong>Skip duplicates:<\/strong> If the current element is the same as the previous one and not at the starting index of the loop, skip it.<\/li>\n            <\/ul>\n        <\/li>\n        <li><strong>Include<\/strong> the current element, recurse, then <code>backtrack<\/code> (remove last element).\/li>\n    <\/ul>\n\n    <h2>Time Complexity:<\/h2>\n    <li><p><strong>Time Complexity = O(n*2<sup>n<\/sup>)<\/strong><\/p><\/li> \n    <h2>Space Complexity:<\/h2>\n    <li><p><strong>Space Complexity = O(n*2<sup>n<\/sup>) for recursion + O(n!) output storage.<\/strong><\/p><\/li>\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\n  <p><strong>Input:<\/strong> <code>arr = [1, 2, 2]<\/code><\/p>\n\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 Function backtrackUniqueSubsets([1, 2, 2])\nSort arr \u2192 arr = [1, 2, 2]\n\nInitialize:\nresult = []\npath = []\n\nCall backtrack([], 0)\n\u2192 Push [] \u2192 result = [[]]\n\nLoop i = 0 \u2192 arr[0] = 1\npath.push(1) \u2192 path = [1]\nCall backtrack([1], 1)\n  \u2192 Push [1] \u2192 result = [[], [1]]\n\n  Loop i = 1 \u2192 arr[1] = 2\n  path.push(2) \u2192 path = [1, 2]\n  Call backtrack([1, 2], 2)\n    \u2192 Push [1, 2] \u2192 result = [[], [1], [1, 2]]\n\n    Loop i = 2 \u2192 arr[2] = 2\n    Condition: i > start && arr[i-1] === arr[i] \u2192 FALSE\n    path.push(2) \u2192 path = [1, 2, 2]\n    Call backtrack([1, 2, 2], 3)\n      \u2192 Push [1, 2, 2] \u2192 result = [[], [1], [1, 2], [1, 2, 2]]\n    Loop ends (start = 3 >= n)\n    path.pop() \u2192 path = [1, 2]\n\n  Loop ends\n  path.pop() \u2192 path = [1]\n\n  Loop i = 2 \u2192 arr[2] = 2\n  Condition: i > start && arr[i-1] === arr[i] \u2192 TRUE (skip duplicate)\n\nLoop ends\npath.pop() \u2192 path = []\n\nLoop i = 1 \u2192 arr[1] = 2\npath.push(2) \u2192 path = [2]\nCall backtrack([2], 2)\n  \u2192 Push [2] \u2192 result = [..., [2]]\n\n  Loop i = 2 \u2192 arr[2] = 2\n  Condition: i > start && arr[i-1] === arr[i] \u2192 FALSE\n  path.push(2) \u2192 path = [2, 2]\n  Call backtrack([2, 2], 3)\n    \u2192 Push [2, 2] \u2192 result = [..., [2, 2]]\n  Loop ends\n  path.pop() \u2192 path = [2]\n\nLoop ends\npath.pop() \u2192 path = []\n\nLoop i = 2 \u2192 arr[2] = 2\nCondition: i > start && arr[i-1] === arr[i] \u2192 TRUE (skip duplicate)\n\nLoop ends\n\nStep 3: End\nReturn result = [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]\n  <\/pre>\n\n  <p><strong>Output:<\/strong> \n    <code>[[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]<\/code>\n  <\/p>\n\n  <p><strong>Explanation:<\/strong> The array is sorted first so duplicates are adjacent. During backtracking, the condition \n    <code>if (i > start && arr[i-1] === arr[i]) continue;<\/code> ensures that duplicate elements at the same recursion depth are skipped, preventing duplicate subsets.\n  <\/p>\n  \n<\/div>\n\n<\/div>\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 subsetsWithDup = function(arr) {\n    let result = [];\n    arr.sort((a,b) => (a-b));\n    let backtrack = (path, start) => {\n        result.push([...path]);\n        for(let i=start;  i<arr.length; i++){\n            if(i > start && arr[i-1] === arr[i])\n            continue;\n            \n            path.push(arr[i]);\n            backtrack(path, i + 1);\n            path.pop();\n        }\n    }\n    backtrack([], 0)\n    return result;\n};\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n<pre><code class=\"language-python\">\ndef subsetsWithDup(arr):\n    arr.sort()\n    result = []\n\n    def backtrack(path, start):\n        result.append(path[:])\n        for i in range(start, len(arr)):\n            if i > start and arr[i] == arr[i - 1]:\n                continue\n            path.append(arr[i])\n            backtrack(path, i + 1)\n            path.pop()\n\n    backtrack([], 0)\n    return result\n\n# Example usage\narr = [1, 2, 2]\nprint(subsetsWithDup(arr))\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n<pre><code class=\"language-java\">\nimport java.util.*;\n\npublic class Main {\n    static void backtrack(int[] arr, List<Integer> path, List<List<Integer>> result, int start) {\n        result.add(new ArrayList<>(path));\n        for (int i = start; i < arr.length; i++) {\n            if (i > start && arr[i] == arr[i - 1]) continue;\n            path.add(arr[i]);\n            backtrack(arr, path, result, i + 1);\n            path.remove(path.size() - 1);\n        }\n    }\n\n    static List<List<Integer>> subsetsWithDup(int[] arr) {\n        Arrays.sort(arr);\n        List<List<Integer>> result = new ArrayList<>();\n        backtrack(arr, new ArrayList<>(), result, 0);\n        return result;\n    }\n\n    public static void main(String[] args) {\n        int[] arr = {1, 2, 2};\n        List<List<Integer>> res = subsetsWithDup(arr);\n        for (List<Integer> subset : res) {\n            System.out.println(subset);\n        }\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\">\nvoid backtrack(vector<int>& arr, vector<int>& path, vector<vector<int>>& result, int start) {\n    result.push_back(path);\n    for (int i = start; i < arr.size(); i++) {\n        if (i > start && arr[i] == arr[i - 1]) continue;\n        path.push_back(arr[i]);\n        backtrack(arr, path, result, i + 1);\n        path.pop_back();\n    }\n}\nvector<vector<int>> subsetsWithDup(vector<int>& arr) {\n    vector<vector<int>> result;\n    vector<int> path;\n    sort(arr.begin(), arr.end());\n    backtrack(arr, path, result, 0);\n    return result;\n}\nint main() {\n    vector<int> arr = {1, 2, 2};\n    vector<vector<int>> res = subsetsWithDup(arr);\n    for (auto &subset : res) {\n        for (int num : subset) cout << num << \" \";\n        cout << endl;\n    }\n}\n<\/code><\/pre>\n<\/div>\n\n<div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n<pre><code class=\"language-c\">\nint cmp(const void* a, const void* b) {\n    return (*(int*)a - *(int*)b);\n}\nvoid backtrack(int* arr, int arrSize, int* path, int pathSize, int start) {\n    \/\/ Print current subset\n    for (int i = 0; i < pathSize; i++) printf(\"%d \", path[i]);\n    printf(\"\\n\");\n\n    for (int i = start; i < arrSize; i++) {\n        if (i > start && arr[i] == arr[i - 1]) continue;\n        path[pathSize] = arr[i];\n        backtrack(arr, arrSize, path, pathSize + 1, i + 1);\n    }\n}\nint main() {\n    int arr[] = {1, 2, 2};\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n    qsort(arr, n, sizeof(int), cmp);\n\n    int path[n];\n    backtrack(arr, n, path, 0, 0);\n    return 0;\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.Collections.Generic;\n\nclass Program {\n    static void Backtrack(int[] arr, List<int> path, List<IList<int>> result, int start) {\n        result.Add(new List<int>(path));\n        for (int i = start; i < arr.Length; i++) {\n            if (i > start && arr[i] == arr[i - 1]) continue;\n            path.Add(arr[i]);\n            Backtrack(arr, path, result, i + 1);\n            path.RemoveAt(path.Count - 1);\n        }\n    }\n    static IList<IList<int>> SubsetsWithDup(int[] arr) {\n        Array.Sort(arr);\n        var result = new List<IList<int>>();\n        Backtrack(arr, new List<int>(), result, 0);\n        return result;\n    }\n    static void Main() {\n        int[] arr = {1, 2, 2};\n        var subsets = SubsetsWithDup(arr);\n        foreach (var subset in subsets) {\n            Console.WriteLine(string.Join(\" \", subset));\n        }\n    }\n}\n<\/code><\/pre>\n<\/div>\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 that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Example 1: Input:nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]] Example 2: Input: nums = [0] Output:[[],[0]] Constraints: 1 start &#038;&#038; arr[i-1] === arr[i] \u2192<\/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,260,176,175,211,811,810,174,172,173,1149],"tags":[],"class_list":["post-9361","post","type-post","status-publish","format-standard","category-algorithms","category-c-c-plus-plus","category-csharp","category-cplusplus","category-data-structures","category-data-structures-and-algorithms","category-dsa","category-java","category-javascript","category-python","category-security-protection"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9361","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=9361"}],"version-history":[{"count":6,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9361\/revisions"}],"predecessor-version":[{"id":10326,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/9361\/revisions\/10326"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=9361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=9361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=9361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}