1723. Find Minimum Time to Finish All Jobs

DFS with pruning

T: O(k^n), n is jobs array size, but with lots pruning, beats 88%

S: O(n), recursion stack

class Solution {
    int res = Integer.MAX_VALUE;
    public int minimumTimeRequired(int[] jobs, int k) {
        
        Arrays.sort(jobs); // prune1, put large one first, quick fail
        reverse(jobs);
        
        dfs(jobs, 0, new int[k]);
        return res;
    }
    private void dfs(int[] jobs, int start, int[] bucket) {
        
        if (start == jobs.length) {
            res = Math.min(res, calMax(bucket));
            return;
        }
        
        for (int i = 0; i < bucket.length; i++) {
            if (i > 0 && bucket[i] == bucket[i - 1]) { // prune2: when try, pass duplicate data
                continue; 
            }
            if (calMax(bucket) >= res) { // prune3: if combination's max is bigger than result, pass
                continue;
            }
            bucket[i] += jobs[start];
            dfs(jobs, start+1, bucket);
            bucket[i] -= jobs[start];
        }
    }
    
    // cal in bucket, the max value now
    private int calMax(int[] bucket) {
        int max = 0;
        for (int i = 0; i < bucket.length; i++) {
            max = Math.max(max, bucket[i]);
        }
        return max;
    }
    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--;
        }
    }
}

bucket:[0, 0, 0], start:0
bucket:[3, 0, 0], start:1
bucket:[6, 0, 0], start:2
bucket:[8, 0, 0], start:3
res:8
bucket:[6, 2, 0], start:3
res:6
bucket:[3, 3, 0], start:2
bucket:[5, 3, 0], start:3
res:5
bucket:[3, 3, 2], start:3
res:3

/*
                 jobs : [3 2 3]
                 
                 jobs dispatch to 3 bucket
             /.  
        [0,0,0]                                     start = 0
         /
       [3,0,0]                                      start = 1
        /
     [6,0,0]              [3, 3, 0]                 start = 2
     / 
     [8, 0, 0]          [5, 3, 0]    [6, 2, 0]      bucket:[3, 3, 2], start:3 start = 3
     cal res = 8        cal res = 5  cal res = 6    cal res = 3
     
     
     // in this case, don't keep going
     if (calMaxBucket(bucket) >= res) {
          continue;
      }
*/