Matchsticks to Square

Question

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.

Solution

一開始自己是用類似 backtracking 的方法做，有通過大概 2/3 的測項，但其實自己寫的有點複雜，也覺得不該需要這麼複雜，所以直接看解答。解答基本上就是用 DFS 去做，看解答的過程中，還是覺得自己遞迴的觀念沒有到非常清楚，其實這題說穿了就很簡單：去看當前這個 nums[i] 該擺在 sum1-sum4 哪個位置而已。由於是正方形，所以很簡單就可以透過算出 nums 的 sum 再除以 4 得到邊長。第二個解法之所以不需要 check sums[3] == width 是因為如果前三個都等於了，那第四個自然等於

    public boolean makesquare(int[] nums) {
        Long sum=0l;
        for(int x:nums){
            sum=sum+x;
        }
        if(sum%4!=0||nums.length<4) return false;
        long width=(sum/4);
        Arrays.sort(nums);
        long sum1=0,sum2=0,sum3=0,sum4=0;
        return helper(nums,nums.length-1,sum1,sum2,sum3,sum4,width);

    }
    public boolean helper(int[] a, int i,long sum1,long sum2,long sum3,long sum4, long width){
        if(sum1>width||sum2>width||sum3>width||sum4>width) return false;
        if(i==-1){
            if(sum1==width&&sum2==width&&sum3==width&&sum4==width) return true;
            else return false;
        }
//check a[i]  belonging to side1,side2,side3,side4
        return helper(a,i-1,sum1+a[i],sum2,sum3,sum4,width)||
        helper(a,i-1,sum1,sum2+a[i],sum3,sum4,width)||
        helper(a,i-1,sum1,sum2,sum3+a[i],sum4,width)||
        helper(a,i-1,sum1,sum2,sum3,sum4+a[i],width);
    }

用 long[] sums 的方法，其實跟上面是一模一樣的東西

    public boolean makesquare(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return false;
        }

        long sum = 0;
        for (long num : nums) {
            sum += num;
        }

        if (sum % 4 != 0) {
            return false;
        }

        long width = sum / 4;
        Arrays.sort(nums);
        long[] sums = new long[4];
        return helper(nums, width, sums, nums.length - 1);
    }

    public boolean helper(int[] nums, long width, long[] sums, int index) {
        if (index == -1) {
            if (sums[0] == width && sums[1] == width && sums[2] == width) {
                return true;
            } else {
                return false;
            }
        }

        for (int i = 0; i < sums.length; i++) {
            if (sums[i] + nums[index] > width) {
                continue;
            }

            sums[i] += nums[index];
            if (helper(nums, width, sums, index - 1)) {
                return true;
            }
            sums[i] -= nums[index];
        }

        return false;
    }