sum - The target sum we are trying to partition.

Input 2: largestNumber - The largest number allowed in a partition for the current recursive call.

Using these variables, the function dynamically adjusts the range of integers it can use to form partitions, ensuring uniqueness by keeping the numbers in progressively non-increasing order.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int helper(int sum, int largestNumber) {\n        // Base Cases\n        if (sum == 0)\n            return 1; // Found one valid partition\n        if (sum < 0 || largestNumber == 0)\n            return 0; // No valid partition\n\n        // Divide-and-Conquer: Include the largestNumber OR exclude it\n        int includeLargest = helper(sum - largestNumber, largestNumber);\n        int excludeLargest = helper(sum, largestNumber - 1);\n\n        return includeLargest + excludeLargest; // Combine both groups\n    }\n\n    int integerPartition(int n) {\n        return helper(n, n); // Call the helper function\n    }\n};\n\n// Example usage\nint main() {\n    Solution solution;\n    int n = 5;\n    cout << \"Number of partitions for \" << n << \": \" << solution.integerPartition(n) << endl;\n    return 0;\n}","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> helper</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> sum</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> largestNumber</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#6A737D;--shiki-dark:#6A737D\">        // Base Cases</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        if</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (sum </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">==</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">)</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">            return</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 1</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span><span style=\"color:#6A737D;--shiki-dark:#6A737D\"> // Found one valid partition</span></span>\n<span class=\"line\"><span sty

Related Tags