1986. Minimum Number of Work Sessions to Finish the Tasks

T: O(k^n), k is number of subset, n is tasks array size, but with pruning, it's fast, beats 100.00%

S: O(n), call stack of recursion

class Solution {
    int min = Integer.MAX_VALUE;
    public int minSessions(int[] tasks, int sessionTime) {
        
        Arrays.sort(tasks);
        reverse(tasks);
        dfs(tasks, 0, new int[tasks.length], sessionTime, 0);
        return min;
    }
    private void dfs(int[] tasks, int start, int[] bucket, int target, int count) {
        
        if (start == tasks.length) {
            min = count; // or min = Math.min(min, count);
            return;
        }
        
        for (int i = 0; i < bucket.length; i++) {
            if (i > 0 && bucket[i-1] == bucket[i]) {
                continue;
            }
            if (tasks[start] + bucket[i] > target) {
                continue;
            }
            if (count >= min) { // 關鍵 pruning, 提前排除大的 count
                continue;
            }
            if(bucket[i] == 0) { // 關鍵, 在這計算 count
                // new task period
                count++;
            }
            
            bucket[i] += tasks[start];
            dfs(tasks, start+1, bucket, target, count);
            bucket[i] -= tasks[start];
        }
        
    }
   
    private void reverse(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}