You are given an integer array jobs, where jobs[i] is the amount of time it takes to complete the ith job.

There are k workers that you can assign jobs to. Each job should be assigned to exactly one worker. The working time of a worker is the sum of the time it takes to complete all jobs assigned to them. Your goal is to devise an optimal assignment such that the maximum working time of any worker is minimized.

Return the minimum possible maximum working time of any assignment. 

&nbsp;
Example 1:

Input: jobs = [3,2,3], k = 3
Output: 3
Explanation: By assigning each person one job, the maximum time is 3.


Example 2:

Input: jobs = [1,2,4,7,8], k = 2
Output: 11
Explanation: Assign the jobs the following way:
Worker 1: 1, 2, 8 (working time = 1 + 2 + 8 = 11)
Worker 2: 4, 7 (working time = 4 + 7 = 11)
The maximum working time is 11.

&nbsp;
Constraints:


	1 &lt;= k &lt;= jobs.length &lt;= 12
	1 &lt;= jobs[i] &lt;= 107


class Solution:
    
    def dfs(self, pos: int, jobs: List[int], workers: List[int]) -> int:
        if pos >= len(jobs):
            return max(workers)
        
        mn = float("inf")
        # we keep track of visited here to skip workers
        # with the same current value of assigned work
		# this is an important step in pruning the number
		# of workers to explore
        visited = set()
        for widx in range(len(workers)):
            
            if workers[widx] in visited:
                continue
            visited.add(workers[widx])
            
            # try this worker
            workers[widx] += jobs[pos]
            
            if max(workers) < mn:
                # if it's better than our previous proceed
                res = self.dfs(pos+1, jobs, workers)
                mn = min(mn, res)
            
            # backtrack
            workers[widx] -= jobs[pos]
        
        return mn
        
    
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
	    # sorting the jobs means that highest value jobs are assigned first
		# and more computations can be skipped by pruning
        jobs.sort(reverse=True)
        return self.dfs(0, jobs, [0] * k)
class Solution {
    int result = Integer.MAX_VALUE;
    public int minimumTimeRequired(int[] jobs, int k) {
        int length = jobs.length;
        Arrays.sort(jobs);
        backtrack(jobs, length - 1, new int [k]);
        return result;
    }
    
    public void backtrack(int [] jobs, int current, int [] workers) {
        if (current < 0) {
            result = Math.min(result, Arrays.stream(workers).max().getAsInt());
            return;
        }
        
        if (Arrays.stream(workers).max().getAsInt() >=  result)
            return;
        for (int i=0; i<workers.length; i++) {
            if (i > 0 && workers[i] == workers[i-1])
                continue;
            // make choice
            workers[i] += jobs[current];
            // backtrack
            backtrack(jobs, current-1, workers);
            // undo the choice
            workers[i] -= jobs[current];
        }
    }
    
    
}
class Solution {
public:
    int minimumTimeRequired(vector<int>& jobs, int k) {
        int sum = 0;
        for(int j:jobs)
            sum += j;
        sort(jobs.begin(),jobs.end(),greater<int>());
        int l = jobs[0], r = sum;
        while(l<r){
            int mid = (l+r)>>1;
            vector<int> worker(k,0);
            if(dfs(jobs,worker,0,mid))
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
    bool dfs(vector<int>& jobs, vector<int>& worker, int step, int target){
        if(step>=jobs.size())
            return true;
        int cur = jobs[step];
        // assign cur to worker i
        for(int i=0;i<worker.size();i++){
            if(worker[i] + cur <= target){
                worker[i] += cur;
                if(dfs(jobs,worker,step+1,target))
                    return true;
                worker[i] -= cur;
            }
            if(worker[i]==0)
                break;
        }
        return false;
    }
};
var minimumTimeRequired = function(jobs, k) {
    let n=jobs.length, maskSum=[...Array(1<<n)].map(d=>0)
    for(let mask=0;mask<(1<<n);mask++) //pre-store the sums of every mask
        for(let i=0;i<n;i++)
            maskSum[mask]+=Number(((1<<i) & mask)!=0)*jobs[i]
    let dp=[...Array(k+1)].map(d=>[...Array(1<<n)].map(d=>Infinity))
    dp[0][0]=0
    for(let i=1;i<=k;i++) //for each new person
        for(let curmask=0;curmask<(1<<n);curmask++) //guess what his mask can be, what items can he select
            for(let prevmask=0;prevmask<(1<<n);prevmask++) // but also, guess what the previous i-1 persons took already
                if((curmask&prevmask)===0) //obviously, 2 people can't take the same job
                    dp[i][curmask|prevmask]=Math.min(dp[i][curmask|prevmask],Math.max(dp[i-1][prevmask],maskSum[curmask]))
    return dp[k][(1<<n) -1]
};
Find Minimum Time to Finish All Jobs