Fork me on GitHub

Partition to K Equal Sum Subsets

Posted on

Description

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (sum % k) return false;
        int target = sum / k;
        vector<bool> visited(nums.size(), false);
        return helper(target, nums, visited, k, 0, 0);
    }
    
    bool helper(int target, vector<int>& nums, vector<bool>& visited, int k, int currentSum, int start) {
        if (k == 0) return true;
        if (target == currentSum) return helper(target, nums, visited, k - 1, 0, 0);
        for (int i = start; i < nums.size(); i++) {
            if (visited[i] == true) continue;
            visited[i] = true;
            if ( helper(target, nums, visited, k, currentSum + nums[i], i + 1) ) return true;
            visited[i] = false;
        }
        return false;
    }
};