LeetCode(473) -- Matchsticks to Square

Problem

给了一些火柴棍的长度，判断它们能否拼成一个正方形。

Solution

public class P473_MatchstickstoSquare {

    public HashMap<Pair<Integer, Integer>, Boolean> memo = new HashMap<>();

    public int[] nums;

    public int side;

    public boolean recurse(Integer mask, Integer sidesDone) {
        int total = 0;
        int L = this.nums.length;

        Pair<Integer, Integer> memoKey = new Pair<>(mask, sidesDone);
        for (int i = L - 1; i >= 0; i--) {
            if ((mask & (1 << i)) == 0) {
                total += this.nums[L - 1 - i];
            }
        }
        if (total > 0 && total % this.side == 0) {
            sidesDone++;
        }
        if (sidesDone == 3) {
            return true;
        }
        if (this.memo.containsKey(memoKey)) {
            return this.memo.get((memoKey));
        }
        boolean ans = false;
        int c = total / this.side;
        int rem = this.side * (c + 1) - total;
        for (int i = L - 1; i >= 0; i--) {
            if (this.nums[L - 1 - i] <= rem && (mask & (1 << i)) > 0) {
                if (recurse(mask ^ (1 << i), sidesDone)) {
                    ans = true;
                    break;
                }
            }
        }
        this.memo.put(memoKey, ans);
        return ans;
    }

    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int L = nums.length;
        int perimeter = 0;
        for (int num : nums) {
            perimeter += num;
        }
        if (perimeter % 4 != 0) {
            return false;
        }
        this.nums = nums;
        this.side = perimeter / 4;
        return this.recurse((1 << L) - 1, 0);
    }
}

61%

The Best Solution

class Solution {
     public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4)
            return false;
        int sum = 0;
        for (int n : nums)
            sum += n;
        if (sum % 4 != 0)
            return false;
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        return canMakeSquare(nums, nums.length - 1, 0, sum / 4, 0, used);
    }

    // side: there are 4 side of a square to be filled
    private boolean canMakeSquare(int[] nums, int idx, int sum, int targetSum, int side, boolean[] used) {
        // if there is only 1 side left, since all the rest reaches target, the last one reaches targetSum for sure
        if (side == 3)
            return true;

        if (sum == targetSum)
            return canMakeSquare(nums, nums.length - 1, 0, targetSum, side + 1, used);
        else if (sum > targetSum)
            return false;
        else 
        {
            for (int i = idx; i >= 0; --i)
            {
                if (used[i])
                    continue;
                used[i] = true;
                if (canMakeSquare(nums, i - 1, sum + nums[i], targetSum, side, used))
                    return true;
                used[i] = false;
                // dedup
                while (i > 0 && nums[i] == nums[i -1])
                    i--;
            }
            return false;
        }
    }
}