473. Matchsticks to Square

same as 698, easier version, k = 4

from numbers' view

T: O(4^n), but with lots of pruning, beats 91%

S: O(n), recursion stack

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int m : matchsticks) {
            sum += m;
        }
        if (sum % 4 != 0) {
            return false;
        }
        Arrays.sort(matchsticks); // prune 0
        reverse(matchsticks);
        return dfs(matchsticks, new int[4], 0, sum/4);
    }
    
    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 buckets status is same, can skip it
            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--;
        }
    }
}

/*
dispatch to 4 bucket
            s 
           [2,2,2,1,1] => cal mean (2+2+2+1+1)/4 = 2 
           
           / /  \. \  index = 0
         2
       / / \ \ index = 1
      2  2'
      x  /\    \   \   index = 2
   > 2  2. 2'  2''
     x  x   x   x   1    index = 3 , value = 1
                    \
       x     x   x   2    index = 4 , value = 1, index = 4 == array.size() => finished
   
   in each bucket, fill data
   each number we have 4 choices (buckets)
   so O(4^n)
   
   for (int i = 0; ~ 4 bucket)
       then for i = 0~ array put
   
   
   what fast? we should sort by desc
*/