package com.fishercoder.solutions;

import java.util.Arrays;

/**
 * 473. Matchsticks to Square
 *
 * Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has,
 * please find out a way you can make one square by using up all those matchsticks.
 * You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.
 * Your input will be several matchsticks the girl has, represented with their stick length.
 * Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

 Example 1:
 Input: [1,1,2,2,2]
 Output: true
 Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

 Example 2:
 Input: [3,3,3,3,4]
 Output: false
 Explanation: You cannot find a way to form a square with all the matchsticks.

 Note:
 The length sum of the given matchsticks is in the range of 0 to 10^9.
 The length of the given matchstick array will not exceed 15.
 */
public class _473 {

    public static class Solution1 {
    /**
     * Partially inspired by: https://discuss.leetcode.com/topic/72107/java-dfs-solution-with-explanation/2
     * One hidden requirement: you'll have to use up all of the given matchsticks, nothing could be left behind.
     */
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }
        Arrays.sort(nums);
        reverse(nums);
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if (sum % 4 != 0) {
            return false;
        }

        return dfs(nums, new int[4], 0, sum / 4);
    }

        private boolean dfs(int[] nums, int[] sums, int index, int target) {
            if (index == nums.length) {
                if (sums[0] == target && sums[1] == target && sums[2] == target) {
                    return true;
                }
                return false;
            }
            for (int i = 0; i < 4; i++) {
                if (sums[i] + nums[index] > target) {
                    continue;
                }
                sums[i] += nums[index];
                if (dfs(nums, sums, index + 1, target)) {
                    return true;
                }
                sums[i] -= nums[index];
            }
            return false;
        }

        private void reverse(int[] nums) {
            int left = 0;
            int right = nums.length - 1;
            while (left < right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
    }

}

@@ -59,1016 +59,8 @@
 s;%0A%0A
-/**%0A * 473. Matchsticks to Square%0A *%0A * Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has,%0A * please find out a way you can make one square by using up all those matchsticks.%0A * You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.%0A * Your input will be several matchsticks the girl has, represented with their stick length.%0A * Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.%0A%0A Example 1:%0A Input: %5B1,1,2,2,2%5D%0A Output: true%0A Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.%0A%0A Example 2:%0A Input: %5B3,3,3,3,4%5D%0A Output: false%0A Explanation: You cannot find a way to form a square with all the matchsticks.%0A%0A Note:%0A The length sum of the given matchsticks is in the range of 0 to 10%5E9.%0A The length of the given matchstick array will not exceed 15.%0A */%0A
 publ
@@ -120,12 +120,20 @@
     
-/**%0A
+    /**%0A    
     
@@ -241,16 +241,20 @@
 /2%0A     
+ 
+   
 * One hi
@@ -362,15 +362,23 @@
     
-*/%0A
+    */%0A   
     
+ 
 publ
@@ -417,24 +417,28 @@
 ) %7B%0A        
+    
 if (nums == 
@@ -468,32 +468,36 @@
 ) %7B%0A            
+  
+  
 return false;%0A  
@@ -502,26 +502,33 @@
         
-%7D%0A
+    %7D%0A   
         
 Arrays.s
@@ -519,16 +519,17 @@
         
+ 
 Arrays.s
@@ -547,16 +547,20 @@
         
+    
 reverse(
@@ -570,24 +570,28 @@
 s);%0A        
+   
+ 
 int sum = 0;
@@ -587,24 +587,28 @@
 nt sum = 0;%0A
+    
         for 
@@ -616,32 +616,36 @@
 int i : nums) %7B%0A
+    
             sum 
@@ -650,34 +650,42 @@
 m += i;%0A        
-%7D%0A
+    %7D%0A    
         if (sum 
@@ -700,32 +700,36 @@
 ) %7B%0A            
+    
 return false;%0A  
@@ -726,35 +726,43 @@
  false;%0A        
-%7D%0A%0A
+    %7D%0A%0A    
         return d
@@ -795,16 +795,20 @@
 m / 4);%0A
+    
     %7D%0A%0A 

refactor 473