Matchsticks to Square, C++, DFS


  • 0
    class Solution {
    public:
        bool helper(vector<int>& nums, vector<int>& visited, vector<int>& sides, int eachSide, int curPos) {
            if(sides[curPos]==eachSide) {
                if(curPos==3) return true;
                else curPos++;
            }
            for(int i=0;i<nums.size();i++) {
                if(visited[i]==1) continue;
                if(sides[curPos]+nums[i]>eachSide) break;
                sides[curPos] += nums[i];
                visited[i] = 1;
                if(helper(nums,visited,sides,eachSide,curPos)) return true;
                visited[i] = 0;
                sides[curPos] -= nums[i];
            }         
            return false;
        }
        bool makesquare(vector<int>& nums) {
            int len = nums.size();
            if(len==0) return false;
            vector<int> visited(len,0);
            vector<int> sides(4,0);
            int sum = 0;
            for(int n : nums) sum += n;
            if(sum % 4 != 0) return false;
            int eachSide = sum/4;
            return helper(nums,visited,sides,eachSide,0);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.