473. Matchsticks to Square

Description

You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Constraints

• 1 <= matchsticks.length <= 15

• 0 <= matchsticks[i] <= 109

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: matchsticks = [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: matchsticks = [3, 3, 3, 3, 4]

Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean makesquare(int[] matchsticks) {
        if(matchsticks == null || matchsticks.length < 4) {
            return false;
        }
        int sum = 0;
        for(int matchstick: matchsticks) {
            sum += matchstick;
        }
        if(sum%4 != 0) {
            return false;
        }
        return makesquare(matchsticks, 0, sum/4, new int[4]);
    }
    
    private boolean makesquare(int[] matchsticks, int index, int target, int[] sides) {
        if(index == matchsticks.length) {
            if(sides[0] == target && sides[1] == target && 
                    sides[2] == target && sides[3] == target) {
                return true;
            }
            return false;
        }
        for(int i = 0; i < 4; i++) {
            if(sides[i] + matchsticks[index] > target) {
                continue;
            }
            sides[i] += matchsticks[index];
            if(makesquare(matchsticks, index+1, target, sides)) {
                return true;
            }
            sides[i] -= matchsticks[index];
        }
        return false;
    }
}

Follow up