Tricky question leetcode well written 👏 and for the record Beats 100%
Tricky question from 698. Partition to K Equal Sum Subsets leetcode well written \uD83D\uDC4F\n\nThe explanation may be lenthy .. but its woth explaining to the
Tricky question from 698. Partition to K Equal Sum Subsets leetcode well written \uD83D\uDC4F\n\nThe explanation may be lenthy .. but its woth explaining to the interviewer \n\nHave fun with this one \uD83C\uDF40\uD83D\uDE80\n\n[For the record Beats 100% ](https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/submissions/1371119847)\n\n# Code\n```java []\n//Approach -1\nclass Solution {\n    private int minSessions;\n\n    public int minSessions(int[] tasks, int sessionTime) {\n        minSessions = tasks.length;\n        int[] sessions = new int[tasks.length];\n        backtrack(tasks.length - 1, tasks, sessions, sessionTime);\n        return minSessions;\n    }\n\n    private void backtrack(int index, int[] tasks, int[] sessions, int sessionTime) {\n        if (index < 0) {\n            int usedSessions = 0;\n            for (int session : sessions) {\n                if (session > 0) usedSessions++;\n            }\n            minSessions = Math.min(minSessions, usedSessions);\n            return;\n        }\n        for (int i = 0; i < sessions.length; i++) {\n            if (i > 0 && sessions[i] == sessions[i-1]) continue;\n            if (sessions[i] + tasks[index] <= sessionTime) {\n                sessions[i] += tasks[index];\n                backtrack(index - 1, tasks, sessions, sessionTime);\n                sessions[i] -= tasks[index];\n            }\n            if (sessions[i] == 0) break;\n        }\n    }\n}\n\n```\n```java []\n//Approach -2\nclass Solution {\n    private int minSessions;\n\n    public int minSessions(int[] tasks, int sessionTime) {\n        minSessions = tasks.length; // Worst case: one session per task\n        int[] sessions = new int[tasks.length];\n        \n        // Sort tasks in descending order\n        //Arrays.sort(tasks);\n        //reverse(tasks);\n        \n        backtrack(0, tasks, sessions, 0, sessionTime);\n        return minSessions;\n    }\n\n    private void backtrack(int index, int[] tasks, int[] sessions, int usedSessions, int sessionTime) {\n        if (usedSessions >= minSessions) {\n            return; // Early termination\n        }\n\n        if (index == tasks.length) {\n            minSessions = Math.min(minSessions, usedSessions);\n            return;\n        }\n\n        for (int i = 0; i < sessions.length; i++) {\n            if (i > 0 && sessions[i] == sessions[i-1]) continue; // Skip duplicate assignments\n            \n            if (sessions[i] + tasks[index] <= sessionTime) {\n                sessions[i] += tasks[index];\n                backtrack(index + 1, tasks, sessions, Math.max(usedSessions, i + 1), sessionTime);\n                sessions[i] -= tasks[index];\n            }\n            \n            if (sessions[i] == 0) break; // Optimization: no need to try empty sessions\n        }\n    }\n\n    private void reverse(int[] arr) {\n        int left = 0, right = arr.length - 1;\n        while (left < right) {\n            int temp = arr[left];\n            arr[left] = arr[right];\n            arr[right] = temp;\n            left++;\n            right--;\n        }\n    }\n}\n\n```\n\n```java []\n\n// Approach - 3\n\n\nclass Solution {\n    private int minSessions;\n\n    public int minSessions(int[] tasks, int sessionTime) {\n        minSessions = tasks.length; // Worst case: one session per task\n        int[] sessions = new int[tasks.length];\n        \n        // Sort tasks in descending order\n        Arrays.sort(tasks);// Not mandatory\n        reverse(tasks); // Not mandatory\n        \n        backtrack(0, tasks, sessions, 0, sessionTime);\n        return minSessions;\n    }\n\n    private void backtrack(int index, int[] tasks, int[] sessions, int usedSessions, int sessionTime) {\n        if (usedSessions >= minSessions) {\n            return; // Early termination\n        }\n\n        if (index == tasks.length) {\n            minSessions = Math.min(minSessions, usedSessions);\n            return;\n        }\n\n        for (int i = 0; i < usedSessions + 1; i++) {\n            if (i > 0 && sessions[i] == sessions[i-1]) continue; // Skip duplicate assignments\n            \n            if (sessions[i] + tasks[index] <= sessionTime) {\n                sessions[i] += tasks[index];\n                backtrack(index + 1, tasks, sessions, Math.max(usedSessions, i + 1), sessionTime);\n                sessions[i] -= tasks[index];\n            }\n            \n            if (sessions[i] == 0) break; // Optimization: no need to try empty sessions\n        }\n    }\n\n    private void reverse(int[] arr) {\n        int left = 0, right = arr.length - 1;\n        while (left < right) {\n            int temp = arr[left];\n            arr[left] = arr[right];\n            arr[right] = temp;\n            left++;\n            right--;\n        }\n    }\n}\n\n/*\nThe reason for using i < usedSessions + 1 instead of i < sessions.length is related to how we\'re managing the sessions in this backtracking approach. Here\'s the detailed explanation:\n\nusedSessions represents the number of sessions we\'re currently using.\nWhen we\'re deciding where to place the current task, we have two options:\na) Put it in one of the existing sessions (0 to usedSessions - 1)\nb) Start a new session (which would be at index usedSessions)\nBy using i < usedSessions + 1, we\'re allowing the algorithm to:\n\nTry all existing sessions (0 to usedSessions - 1)\nPotentially start one new session (at index usedSessions)\n\n\nIf we used i < sessions.length, we would be considering all possible sessions up to the maximum number of tasks, which is inefficient because:\n\nWe know we won\'t need more sessions than there are tasks\nMany of these sessions would be empty and unnecessary to consider\n\n\nBy limiting our search to usedSessions + 1, we\'re pruning the search space significantly, which improves the efficiency of the algorithm.\n\nThis approach ensures that we\'re only considering relevant sessions at each step of the backtracking process. It\'s a form of optimization that keeps the algorithm focused on the most promising solutions.\nTo illustrate with an example:\n\nIf we have 5 tasks and we\'re currently using 2 sessions\nusedSessions + 1 would be 3, so we\'d consider sessions 0, 1, and potentially start a new one at 2\nWe wouldn\'t need to consider sessions 3 and 4 at this point, as they would definitely be empty\n\nThis optimization is particularly effective when combined with the early termination checks and the strategy of trying to fill existing sessions before starting new ones.\n\n*/\n```\n\n**Updated** solution\n\n[698. Partition to K Equal Sum Subsets](https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solutions/5559337/crazy-best-problem-to-solve-must-solve-this-pattern/)\n[2305. Fair Distribution of Cookies](https://leetcode.com/problems/fair-distribution-of-cookies/solutions/5559818/amazing-must-read-please-attach-more-question-of-this-template/)\n[1723. Find Minimum Time to Finish All Jobs](https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs/solutions/5559845/add-more-of-this-template-question-here/)\n[473. Matchsticks to Square](https://leetcode.com/problems/matchsticks-to-square/solutions/5559911/please-add-more-question-that-can-be-solved-by-this-template/)\n\n# Code\n```java []\nclass Solution {\n    public boolean canPartitionKSubsets(int[] nums, int k) {\n        int sum = Arrays.stream(nums).sum();\n        if (sum % k != 0) return false;\n        \n        int targetSum = sum / k;\n        Arrays.sort(nums);\n        // add a reverse it helps!\n        return backtrack(nums.length - 1, nums, new int[k], targetSum);\n    }\n    \n    private boolean backtrack(int index, int[] nums, int[] sums, int targetSum) {\n        if (index < 0) return true;\n        \n        for (int i = 0; i < sums.length; i++) {\n            if (sums[i] + nums[index] > targetSum) continue;\n            \n            sums[i] += nums[index];\n            \n            if (backtrack(index - 1, nums, sums, targetSum)) {\n                return true;\n            }\n            \n            sums[i] -= nums[index];\n            \n            if (sums[i] == 0) break;// why ? explanation given below\n        }\n        \n        return false;\n    }\n}\n/*\nGreat question! The line if (sums[i] == 0) break; is indeed a crucial optimization that can significantly reduce the time complexity in many cases. Let\'s break down why this is so effective:\n\nAvoiding Duplicate Work:\nWhen we backtrack and remove a number from a subset, if that subset becomes empty (sum becomes 0), it means we\'re back to the starting point for that subset. If we continue to the next iteration of the loop, we\'d be trying to add the current number to another empty subset. This would lead to exploring the same combinations we\'ve already explored or will explore in future recursive calls.\nSymmetry Breaking:\nAll empty subsets are identical from the perspective of our algorithm. Once we\'ve tried adding the current number to one empty subset and it didn\'t lead to a solution, there\'s no point in trying to add it to other empty subsets.\nPruning the Search Tree:\nBy breaking the loop when we encounter an empty subset, we\'re effectively pruning a large portion of the search tree. This can drastically reduce the number of recursive calls and iterations.\nReducing Permutations:\nWithout this break, the algorithm would consider all permutations of the subsets, which is unnecessary since we only care about the content of the subsets, not their order.\n\nTime Complexity Impact:\n\nIn the worst case (when no valid partition exists), the time complexity without this optimization could be O(k^n), where k is the number of subsets and n is the number of elements.\nWith this optimization, many redundant paths are eliminated, potentially reducing the time complexity significantly, although it remains exponential in the worst case.\n\nPractical Impact:\n\nFor inputs where many valid solutions exist, this optimization might not make a huge difference.\nHowever, for inputs where valid solutions are sparse or non-existent, this optimization can reduce the runtime from hours or days to seconds or minutes.\n\nExample:\nConsider an array [10, 10, 10, 7, 7, 7, 6, 6, 6] with k = 3. Without the optimization, the algorithm would try many permutations of how to distribute these numbers. With the optimization, once it tries [10, 10, 10] in one subset and backtracks, it immediately knows not to try 10 in the other empty subsets, significantly reducing the search space.\nIn summary, this simple optimization leverages the problem\'s structure to eliminate a vast number of unnecessary recursive calls, making the algorithm much more efficient in practice, especially for challenging inputs.\n*/\n\n```\n```java []\n// To print all such subsets\n\n// This is the very final result\n// To print all such subsets\n\n// This is the very final result\nimport java.util.*;\n\nclass Solution {\n    public boolean canPartitionKSubsets(int[] nums, int k) {\n        int sum = Arrays.stream(nums).sum();\n        if (sum % k != 0) return false;\n        \n        int targetSum = sum / k;\n        Arrays.sort(nums);\n        reverse(nums); // Reverse the array to have larger numbers first\n        \n        List<List<Integer>> subsets = new ArrayList<>();\n        for (int i = 0; i < k; i++) {\n            subsets.add(new ArrayList<>());\n        }\n        \n        boolean result = backtrack(0, nums, subsets, new int[k], targetSum);\n        \n        if (result) {\n            System.out.println("Valid partition found:");\n            for (int i = 0; i < subsets.size(); i++) {\n                System.out.println("Subset " + (i + 1) + ": " + subsets.get(i));\n            }\n        } else {\n            System.out.println("No valid partition found.");\n        }\n        \n        return result;\n    }\n    \n    private boolean backtrack(int index, int[] nums, List<List<Integer>> subsets, int[] sums, int targetSum) {\n        if (index == nums.length) {\n            return true; // All numbers have been used\n        }\n        \n        for (int i = 0; i < subsets.size(); i++) {\n            if (sums[i] + nums[index] > targetSum) continue;\n            if(i>0 && sums[i]==sums[i-1]) continue;\n            \n            subsets.get(i).add(nums[index]); // Add to subset\n            sums[i] += nums[index];          // Update sum\n            \n            if (backtrack(index + 1, nums, subsets, sums, targetSum)) {\n                return true;\n            }\n            \n            sums[i] -= nums[index];          // Revert sum\n            subsets.get(i).remove(subsets.get(i).size() - 1); // Remove from subset\n            \n            if (sums[i] == 0) break; // Optimization: no need to try empty subsets\n        }\n        \n        return false;\n    }\n    \n    private void reverse(int[] nums) {\n        int left = 0, right = nums.length - 1;\n        while (left < right) {\n            int temp = nums[left];\n            nums[left] = nums[right];\n            nums[right] = temp;\n            left++;\n            right--;\n        }\n    }\n}\n```
['Backtracking', 'Java']