<Medium> Matchsticks to Square (LeetCode : C#)

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

📕 문제 설명

성냥개비 정수 배열이 주어지고, 각 배열의 값은 i번째 성냥개비의 길이를 나타낸다. 모든 성냥 개비를 한 번씩만 사용해서 연결할 때 정사각형을 만들 수 있는지에 대한 여부 반환

• Input
  성냥 개비 길이 정보 배열 (int[])
• Output
  모든 성냥 개비 한 번씩만 사용했을 때 정사각형 만들 수 있는지에 대한 여부

예제

풀이

정사각형 만들려면 4변의 길이가 같은지를 보면 된다. 그래서 주어진 배열을 4개의 같은 합으로 나눌 수 있는지 보는 문제다. 그래서 앞에 k partition과 동일하게 백트래킹으로 풀었다.

앞의 k partition에서 k = 4로 고정되어 있는 케이스라고 보면 된다.

public class Solution {
    public bool Makesquare(int[] matchsticks) {
        int sum = matchsticks.Sum();
        if (sum % 4 != 0) return false;
        if (matchsticks.Length < 4) return false;

        bool[] visited= new bool[matchsticks.Length];

        return Search(matchsticks, 4, 0, sum / 4, 0, visited);
    }

    public bool Search(int[] matchsticks, int k, int sum, int target, int start, bool[] visited)
    {
        if (k == 1) return true;
        if (sum == target) return Search(matchsticks, k - 1, 0, target, 0, visited);

        for (int i = start; i < matchsticks.Length; i++)
        {
            int localSum = matchsticks[i] + sum;
            if (localSum > target || visited[i]) continue;
            visited[i] = true;
            if (Search(matchsticks, k, localSum, target, i, visited)) return true;
            visited[i] = false;
        }

        return false;
    }
}

결과