https://leetcode.com/contest/leetcode-weekly-contest-54/problems/partition-to-k-equal-sum-subsets/

1st slow but passed solution

#include <iostream>
#include <limits.h>
#include <vector>
#include <string>
#include <iterator>
#include <map>
#include <queue>
#include <list>
#include <algorithm>
#include <stdio.h>
#include <set>
#include <vector>

using namespace std;

class Solution {
public:
    bool check(vector<int>& nums, int start, vector<int>& remain) {
        bool complete = true;
        for (int i = 0; i < remain.size(); i++) {
            if (remain[i] != 0) {
                complete = false;
                break;
            }
        }
        if (complete) {
            return true;
        }
        for (int i = start; i < nums.size(); i++) {
            for (int j = 0; j < remain.size(); j++) {
                if (remain[j] >= nums[i]) {
                    remain[j] -= nums[i];
                    bool res = check(nums, (i + 1), remain);
                    if (res) {
                        return true;
                    }
                    remain[j] += nums[i];
                }
            }
            return false;
        }
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {

        sort(nums.begin(), nums.end(), greater<int>());

        int total = 0;
        for (int i = 0; i < nums.size(); i++) {
            total += nums[i];
        }
        int target = total / k;
        if (total % k != 0) {
            return false;
        }
        vector<int> remain(k, target);
        bool res = check(nums, 0, remain);
        return res;
    }
};

int main()
{
    //int test[7] = {4, 3, 2, 3, 5, 2, 1};
    int test[4] = {3, 3, 1, 3};
    vector<int> in(test, (test + sizeof(test)/sizeof(int)));
    Solution sol;
    bool r = sol.canPartitionKSubsets(in, 2);
    system("pause");
    return 1;
}