[leetcode]698. Partition to K Equal Sum Subsets

Analysis

终于抽到敬业福啦 哈哈哈—— [每天刷题并不难0.0]

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Explanation:

递归~

Implement

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        int len = nums.size();
        vector<int> visit(len, 0);
        for(int num:nums)
            sum += num;
        if(k<=0 || sum%k!=0)
            return false;
        return helper(nums, visit, 0, k, 0, 0, sum/k);
    }
    bool helper(vector<int>& nums, vector<int>& visit, int s, int k, int cur_sum, int cur_num, int target){
        if(k == 1)
            return true;
        if(cur_sum == target && cur_num>0)
            return helper(nums, visit, 0, k-1, 0, 0, target);
        for(int i=s; i<nums.size(); i++){
            if(!visit[i]){
                visit[i] = 1;
                if(helper(nums, visit, i+1, k, cur_sum+nums[i], cur_num++, target))
                    return true;
                visit[i] = 0;
            }
        }
        return false;
    }
};