473. Matchsticks to Square

 一刷 07/2022

Version #1 Backtracking

一开始写了两个TLE的版本，主要问题是把四个边作为了一个target 的int array，不光outer loop要iterate所有的matchsticks，inner loop还要选择match哪一个边

后来思考了一下这里面其实是将情况重复算了4次的，因为每一种matchstick的combinatino放在哪一个边都是无所谓的，所以不需要选择，而只需要依次放进去

看了答案觉得我和答案的区别是答案是尽可能地用matchstick，而我是每次都从头到尾iterate matchsticks去依次填满每一个边

另外一个bit manipulation的总结就是：

    取某一位 (mask >> i) & 1

    clear某一位 mask &= ~(1 << i)

    set某一位 mask |= (1 << i)

Time O(M*2^M)?

Space O(2^M) for the visited hashset

Runtime: 47 ms, faster than 77.95% of Java online submissions for Matchsticks to Square.

Memory Usage: 43.4 MB, less than 17.51% of Java online submissions for Matchsticks to Square.

class Solution {

    public boolean makesquare(int[] matchsticks) {

        int sum = 0;

        for (int m : matchsticks) {

            sum += m;

        }

        if (sum % 4 != 0) {

            return false;

        }

        int stickMask = (1 << matchsticks.length) - 1;

        return match(matchsticks, sum / 4, 0, 4, new HashSet<>(),  stickMask);

    }

    

    private boolean match(int[] matchsticks, int edgeLength, int currWanted, int wantedCount, Set<Integer> visited, int stickMask) {

        if (stickMask == 0) {

            return true;

        }

        if (visited.contains(stickMask)) {

            return false;

        }

        if (currWanted == 0) {

            currWanted = edgeLength;

            wantedCount--;

        }

        // selected a matchstick

        for (int i = 0; i < matchsticks.length; i++) {

            // used or longer than wanted length

            if (((stickMask >> i) & 1) == 0 || matchsticks[i] > currWanted) {

                continue;

            }

            stickMask &= ~(1 << i);

            if (match(matchsticks, edgeLength, currWanted - matchsticks[i], wantedCount, visited, stickMask)) {

                return true;

            }

            // set the ith bit of the stick mask to 1

            stickMask |= (1 << i);

        }

        visited.add(stickMask);

        return false;

    }

}