Matchsticks to Square Solutions in C++

/// Source : https://leetcode.com/problems/matchsticks-to-square/description/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;


/// Backtracking
/// Time Complexity: O(4^n)
/// Space Complexity: O(n)
class Solution {
public:
    bool makesquare(vector<int>& nums) {

        if(nums.size() == 0)
            return false;

        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 4)
            return false;

        int side = sum / 4;
        vector<int> cur = {side, side, side, side};
        return dfs(nums, 0, cur);
    }

private:
    bool dfs(const vector<int>& nums, int index, vector<int>& cur){

        if(index == nums.size()){
            for(int e: cur)
                if(e)
                    return false;
            return true;
        }

        for(int i = 0; i < cur.size() ; i ++)
            if(cur[i] >= nums[index]){
                cur[i] -= nums[index];
                if(dfs(nums, index + 1, cur))
                    return true;
                cur[i] += nums[index];
            }
        return false;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/matchsticks-to-square/description/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;


/// Backtracking
/// Improvement: Using longer sticks first:)
///
/// Time Complexity: O(4^n)
/// Space Complexity: O(n)
class Solution {
public:
    bool makesquare(vector<int>& nums) {

        if(nums.size() == 0)
            return false;

        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % 4)
            return false;

        int side = sum / 4;
        vector<int> cur = {side, side, side, side};
        sort(nums.begin(), nums.end(), greater<int>());
        return dfs(nums, 0, cur);
    }

private:
    bool dfs(const vector<int>& nums, int index, vector<int>& cur){

        if(index == nums.size()){
            for(int e: cur)
                if(e)
                    return false;
            return true;
        }

        for(int i = 0; i < cur.size() ; i ++)
            if(cur[i] >= nums[index]){
                cur[i] -= nums[index];
                if(dfs(nums, index + 1, cur))
                    return true;
                cur[i] += nums[index];
            }
        return false;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/matchsticks-to-square/description/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <numeric>
#include <vector>
#include <cassert>

using namespace std;


/// Memory Search
///
/// Time Complexity: O(n*2^n)
/// Space Complexity: O(2^n)
class Solution {

private:
    int all, side;

public:
    bool makesquare(vector<int>& nums) {

        if(nums.size() == 0)
            return false;

        int total = accumulate(nums.begin(), nums.end(), 0);
        if(total % 4)
            return false;

        sort(nums.begin(), nums.end(), greater<int>());
        all = (1 << nums.size()) - 1;
        side = total / 4;

        vector<int> sum(all + 1, -1);
        vector<int> dp(all + 1, -1); // -1 - unvisited, 0 - false, 1 - true
        return dfs(nums, 0, dp, sum);
    }

private:
    bool dfs(const vector<int>& nums, int state,
             vector<int>& dp, vector<int>& sum){

        if(state == all)
            return true;

        if(dp[state] != -1)
            return dp[state];

        int left = getSum(nums, state, sum) % side;

        for(int i = 0; i < nums.size() ; i ++)
            if((state & (1 << i)) == 0 && left + nums[i] <= side
               && dfs(nums, state | (1 << i), dp, sum))
                return dp[state] = 1;
        return dp[state] = 0;
    }

    int getSum(const vector<int>& nums, int state, vector<int>& sum){

        if(sum[state] != -1)
            return sum[state];

        if(state == 0)
            return sum[state] = 0;

        for(int i = 0; i < nums.size() ; i ++)
            if(state & (1 << i))
                return sum[state] =  nums[i] + getSum(nums, state - (1 << i), sum);
        assert(false);
        return -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/matchsticks-to-square/description/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;


/// Dynamic Programming
///
/// Time Complexity: O(n*2^n)
/// Space Complexity: O(2^n)
class Solution {

public:
    bool makesquare(vector<int>& nums) {

        if(nums.size() == 0)
            return false;

        int total = accumulate(nums.begin(), nums.end(), 0);
        if(total % 4)
            return false;

        sort(nums.begin(), nums.end(), greater<int>());
        int all = (1 << nums.size()) - 1;
        int side = total / 4;

        vector<int> sum(all + 1, 0);
        for(int i = 1; i <= all; i ++)
            for(int j = 0; j < nums.size() ; j ++)
                if(i & (1 << j)){
                    sum[i] = nums[j] + sum[i - (1 << j)];
                    break;
                }

        // dp[state]: is it possible to make a square from the state.
        vector<bool> dp(all + 1, false);
        dp[0] = true;
        for(int i = 1; i <= all; i ++)
            for(int j = 0; j < nums.size(); j ++)
                if(i & (1 << j) && dp[i - (1 << j)] && sum[i - (1 << j)] % side + nums[j] <= side){
                    dp[i] = true;
                    break;
                }
        return dp[all];
    }
};


int main() {

    return 0;
}