Matchsticks to Square

성냥의 길이가 담긴 벡터를 받고 해당 성냥들을 한번씩 사용하여

정사각형을 만들 수 있는지 판단하는 문제

class Solution {
public:    
    bool Partition(int index, int currentSum, int target,
                   vector<int> &matchsticks, vector<bool> &used, int reaminSide)
    {
        int numberOfSticks = matchsticks.size();
        
        if (reaminSide == 1)
        {
            return true;
        }
        else if (currentSum == target)
        {
            return Partition(0, 0, target, matchsticks, used, reaminSide - 1);
        }
        
        for (int i = index; i < numberOfSticks; i++)
        {
            if (used[i])
            {
                continue;
            }
            
            int newSum{currentSum + matchsticks[i]};
            if (newSum <= target)
            {
                used[i] = true;
                
                if (Partition(i + 1, newSum, target, matchsticks, used, reaminSide))
                {
                    return true;
                }
                
                used[i] = false;
            }
        }
        
        return false;
    }
    
    bool makesquare(vector<int>& matchsticks) {
        
        static const int NumberOfSide = 4;
        
        int target{0};
        for (int &match : matchsticks)
        {
            target += match;
        }
        
        auto dv = div(target, NumberOfSide);
        target = dv.quot;
        
        if (dv.rem != 0)
        {
            return false;
        }

        vector<bool> used(matchsticks.size(), false);
        
        bool result = Partition(0, 0, target, matchsticks, used, NumberOfSide);
        
        return result;
    }
};