Partition to K Equal Sum Subsets

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

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.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4

Output: True

Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Thoughts

能否问把数组分成K份，使得它们的和都一样。分成两份可以直接背包DP，分成K写递推就很麻烦。用DFS搜索所有的可能的subset的和等于sum，满足一个就让K -1。当K == 1时说明已经找到了K -1个sum相等的subset，最后一个subset不用算肯定也是和为sum。

Code

/*
 * @lc app=leetcode id=698 lang=cpp
 *
 * [698] Partition to K Equal Sum Subsets
 *
 * https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/
 *
 * algorithms
 * Medium (43.32%)
 * Likes:    1007
 * Dislikes: 57
 * Total Accepted:    53.2K
 * Total Submissions: 122.2K
 * Testcase Example:  '[4,3,2,3,5,2,1]\n4'
 *
 * 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.
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
 * Output: True
 * Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3),
 * (2,3) with equal sums.
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * 1 <= k <= len(nums) <= 16.
 * 0 < nums[i] < 10000.
 * 
 * 
 */
class Solution {
public:
    bool dfs(vector<int> &nums, int pos, int sum, vector<bool> &visited, const int K, const int T) {
        // 前面K - 1份都满足，最后一份一定也是
        if (K == 1) return true;
        if (sum == 0) return dfs(nums, 0, T, visited, K - 1, T);
        for (int i = pos; i < nums.size(); ++i) {
            if (!visited[i] && (sum - nums[i] >= 0)) {
                visited[i] = true;
                if (dfs(nums, i + 1, sum - nums[i], visited, K, T)) return true;
                visited[i] = false;
            }
        }
        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        vector<bool> visited(nums.size());
        return dfs(nums, 0, sum / k, visited, k, sum / k);
    }
};

Ver.2

为了避免访问过(4,3)再到3时访问(3, 4)的情况，我们可以引入一个startIndex, 表示这次应该从哪开始，并且下次递归在target != 0时只能从index > startIndex里选，这样就避免了(3, 2, 1)的出现，相当于我们对subset内部固定一种顺序(combination)，而subset之间继续permutation。

class Solution {
    private boolean helper(int[] nums, int left, boolean[] visited, int curSize, int t, int start) { 
        if (left == 0) {  
            if (curSize == nums.length) {
                return true;
            } else {
                left = t;
                return helper(nums, t, visited, curSize, t, 0);
            }
        }

        for (int i = start; i < nums.length; i++) {
            if (!visited[i] && left - nums[i] >= 0) {
                visited[i] = true;
                if (helper(nums, left - nums[i], visited, curSize + 1, t, start + 1)) {
                    return true;
                }
                visited[i] = false;
            }
        }

        return false;
    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % k != 0) {
            return false;
        }
        boolean[] visited = new boolean[nums.length];

        return helper(nums, sum / k, visited, 0, sum / k, 0);
    }
}

Ver. 3

把更新curSize替换成更新k能让速度更快。我们每次找到一个满足和为t的subset，即相当于把k - 1. 这样我们能减少检查一个subset的时间。

class Solution {
    private boolean helper(int[] nums, int index, int left, boolean[] visited, int k, int t) {
        if (k == 1) {
            return true;
        }
        if (left == 0) {  
            return helper(nums, 0, t, visited, k - 1, t);
        }   

        for (int i = index; i < nums.length; i++) {
            if (!visited[i] && left - nums[i] >= 0) {
                visited[i] = true;
                if (helper(nums, i + 1, left - nums[i], visited, k, t)) {
                    return true;
                }
                visited[i] = false;
            }
        }

        return false;
    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        if (sum % k != 0) {
            return false;
        }
        boolean[] visited = new boolean[nums.length];

        return helper(nums, 0, sum / k, visited, k, sum / k);
    }
}