[leetcode #473] Matchsticks to Square

Problem

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.

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.

Constraints:

· 1 <= matchsticks.length <= 15
· 1 <= matchsticks[i] <= 10⁸

Idea

오랜만에 리트코드 푸는 걸 다시 시작하려고 한다.

주어진 막대기로 정사각형을 만들 수 있는지 확인하는 문제다. 가능한 모든 경우에 대해 시도하는 dfs 방법을 써서 풀면 된다.

알고리즘은 다음과 같다.

1. 주어진 index에 해당하는 막대기를 이용해 정사각형을 채우는 재귀함수를 만든다. 재귀함수에서는 해당 막대기를 더할 수 있는 변을 찾는다. 막대기를 더한 뒤 다음 index를 인자로 하는 재귀함수를 호출해 계속해서 정사각형 만드는 과정을 진행한다.

2. 모든 막대기가 사용되고 사각형을 이루는 네 변의 길이가 같다면 정사각형이 만들어진 것이므로 true를 리턴한다.

3. 막대기를 더할 때 사각형을 이루고 있는 네 변에 대해 모두 시도를 해본다. 만들어지는 것이 실패했다면 해당 변에서 막대기를 다시 빼고 진행한다.

Solution

import java.util.HashMap;
import java.util.Collections;

class Solution {
    public List<Integer> nums;
    public int[] sums;
    public int possibleSquareSide;

    public Solution() {
        this.sums = new int[4];
    }

    // Depth First Search function.
    public boolean dfs(int index) {

        // If we have exhausted all our matchsticks, check if all sides of the square are of equal length
        if (index == this.nums.size()) {
            return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
        }

        // Get current matchstick.
        int element = this.nums.get(index);

        // Try adding it to each of the 4 sides (if possible)
        for(int i = 0; i < 4; i++) {
            if (this.sums[i] + element <= this.possibleSquareSide) {
                this.sums[i] += element;
                if (this.dfs(index + 1)) {
                    return true;
                }
                this.sums[i] -= element;
            }
        }

        return false;
    }

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

        // Find the perimeter of the square (if at all possible)
        int L = nums.length;
        int perimeter = 0;
        for(int i = 0; i < L; i++) {
            perimeter += nums[i];
        }

        this.possibleSquareSide =  perimeter / 4;
        if (this.possibleSquareSide * 4 != perimeter) {
            return false;
        }

        // Convert the array of primitive int to ArrayList (for sorting).
        this.nums = Arrays.stream(nums).boxed().collect(Collectors.toList());
        Collections.sort(this.nums, Collections.reverseOrder());
        return this.dfs(0);
    }
}

Time Complexity: O(4ᴺ)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/matchsticks-to-square/