698. Partition to K Equal Sum Subsets

refer this!

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

經典題目

from bucket view

T: O(k*2^n)

S: O(n)

We have used an extra array of size N to mark the already used elements.

And the recursive tree makes at most N calls at one time, so the recursive stack also takes O(N) space

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0) {
            return false;
        }
        Arrays.sort(nums); // prunin
        reverse(nums);
        return dfs(k, nums, 0, 0, new boolean[16], sum/k);
    }
    
    private boolean dfs(int k, int[] nums, int start, int sum, boolean[] visited, int mean) {
        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, mean);
        }
        
        int last = -1;
        for (int i = start; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            if (sum + nums[i] > mean) { // pruning
                continue;
            }
            if (nums[i] == last) { // pruning : skip same number
                continue;
            }
            visited[i] = true;
            sum += nums[i];
            
            last = nums[i]; 
            if (dfs(k, nums, start + 1, sum, visited, mean)) {
                return true;
            }
            
            sum -= nums[i];
            visited[i] = false;
        }
        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--;
        }
    }
}

from numbers view

T: O(k^n), with pruning beats 92%

S: O(n)

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int m : nums) {
            sum += m;
        }
        if (sum % k != 0) {
            return false;
        }
        Arrays.sort(nums); // prune 0
        reverse(nums);
        return dfs(nums, new int[k], 0, sum/k);
    }
    
    private boolean dfs(int[] matchsticks, int[] buckets, int start, int target) {
        if (start == matchsticks.length) {
            return true;
        }
        
        for (int i = 0; i < buckets.length; i++) {
            if (i > 0 && buckets[i-1] == buckets[i]) { // prune 1, 這個 prune 差超多的
                continue;
            }
            if (buckets[i] + matchsticks[start] > target) { // prune 2
                continue;
            }
            buckets[i] += matchsticks[start];
            if (dfs(matchsticks, buckets, start+1, target)) {
                return true;
            }
            buckets[i] -= matchsticks[start];
        }
        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--;
        }
    }
}