dispatch to k subsets or ? subsets

One branch cutting trick to solve three LeetCode questions

Loading...LeetCode

template about DFS in subset

https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247490981&idx=1&sn=db17864d2f6f189d63e051e434c05460&scene=21#wechat_redirect

1. from number view's template

理論上時間複雜度較高, 但蠻多題目需要從數字角度去做的...因為 subset 數量不是確定的, 這題是確定, 但還是從數字出發(好像剪枝效果比較好

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++) {
            // skip duplicate 
            if (i > 0 && bucket[i] == bucket[i - 1]) { // prune2: when try, pass duplicate data
                continue; 
            }
            // 不入 bukcet 的條件
            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]; // backtracking
        }
    }
    
    // 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--;
        }
    }
}

2. from bucket view's template

差別在於是用 visited 來控制 array 值是否被用過, 理論上時間複雜度比較好, 因為是選或不選

O(k*2^k), k 是 subset size

但遇到 subset 不固定時, 應該就無法用了

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        ....get target
        Arrays.sort(nums);
        reverse(nums);
        return dfs(k, nums, 0, 0, new boolean[16], target);
    }
    
    private boolean dfs(int k, int[] nums, int start, 
                    int sum, boolean[] visited, int target) {
        if (k == 0) {
            return true;
        }
        // 換下個 group, set start = 0, sum = 0
        // 為什麼可以設 start 從 0 開始跑呢, 因為有紀錄 visited, 所以使用過的, 會跳過, 所以從 0 開始
        // sum = 0 很直觀, 因為要來計算下個 group 的和到 mean 了沒 
        if (sum == mean) {
            return dfs(k-1, nums, 0, 0, visited, target);
        }
        
        int last = -1; // 去重
        for (int i = start; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (sum + nums[i] > target) {
                continue;
            }
            if (nums[i] == last) { // 去重
                continue;
            }
            
            visited[i] = true; 
            last = nums[i];
            if (dfs(k, nums, start + 1, sum + nums[i], visited, target)) {
                return true;
            }
            visited[i] = false; // backtracking
        }
        return false;
    }
    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--;
        }
    }
}