<p>You are given an integer array <code>jobs</code>, where <code>jobs[i]</code> is the amount of time it takes to complete the <code>i<sup>th</sup></code> job.</p>

<p>There are <code>k</code> workers that you can assign jobs to. Each job should be assigned to <strong>exactly</strong> one worker. The <strong>working time</strong> 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 <strong>maximum working time</strong> of any worker is <strong>minimized</strong>.</p>

<p><em>Return the <strong>minimum</strong> possible <strong>maximum working time</strong> of any assignment. </em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> jobs = [1,2,4,7,8], k = 2
<strong>Output:</strong> 11
<strong>Explanation:</strong> 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.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= jobs.length &lt;= 12</code></li>
	<li><code>1 &lt;= jobs[i] &lt;= 10<sup>7</sup></code></li>
</ul>

class Solution:
    def minimumTimeRequired(self, jobs: List[int], k: int) -> int:
        def dfs(curr_job_index):
            nonlocal min_time
            # Base case: all jobs have been assigned
            if curr_job_index == len(jobs):
                # Update the minimum time if a better solution is found
                min_time = min(min_time, max(workers_load))
                return
            # Try assigning current job to each worker one by one
            for worker in range(k):
                # Pruning: skip if current assignment exceeds the known minimum time
                if workers_load[worker] + jobs[curr_job_index] >= min_time:
                    continue
                # Assign job to worker
                workers_load[worker] += jobs[curr_job_index]
                # Recursively assign the next job
                dfs(curr_job_index + 1)
                # Backtrack: Remove job from worker (undo assignment)
                workers_load[worker] -= jobs[curr_job_index]
                # If worker hadn't been assigned any job before, then this is the least loaded they can be
                # No need to try assigning jobs to other workers with the same load as it'll be equivalent
                if workers_load[worker] == 0:
                    break
        # Initialize each worker's load as 0
        workers_load = [0] * k
        # Sort the jobs in descending order to optimize the search (using greedy aproach)
        #jobs.sort(reverse=True)
        jobs.sort()
        min_time = sys.maxsize
        dfs(0)
        return min_time
952