473. Matchsticks to Square

Link

Solution

Find all possible combinations by the DFS backtrace.

 public boolean makesquare(int[] nums) {
        int sum = 0;
        if(nums == null || nums.length < 4) return false;
        for(int i : nums){
            sum += i;
        }
        if(sum % 4 != 0) return false;
        
        //optimal
        // Arrays.sort(nums);
        // reverse(nums);
        
        
        return dfs(nums, 0, new int[4], sum/4);
    }

    public boolean dfs(int[] nums, int index, int[] edges, int target){
        if(index == nums.length && edges[0] == edges[1] && edges[1] == edges[2]
          && edges[2] == edges[3] && edges[0] == target){
            return true;
        }
        //all possiblities
        for(int i = 0; i < 4; i ++){
            if(target >= edges[i] + nums[index]){
                edges[i] += nums[index];
                if(dfs(nums, index+1, edges, target)) return true;
                edges[i] -= nums[index]; 
            }
        }
        return false;
    }
       
    public void reverse(int[] nums){
        int n = nums.length-1;
        for(int i = 0; i < nums.length/2; i++){
            int swap = nums[n-i];
            nums[n-i] = nums[i];
            nums[i] = swap;
        }
        
    }