Partition to K Equal Sum Subsets

佚名 6年前 (2019-05-06) 随笔 1343人围观抢沙发百度已收录

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:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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.

Assume sum is the sum of nums[] . The dfs process is to find a subset of nums[] which sum equals to sum/k. We use an array visited[] to record which element in nums[] is used. Each time when we get a cur_sum = sum/k, we will start from position 0 in nums[] to look up the elements that are not used yet and find another cur_sum = sum/k.

 1 class Solution {
 2     public boolean canPartitionKSubsets(int[] nums, int k) {
 3         int sum = 0;
 4         for (int num : nums) sum += num;
 5         if (k <= 0 || sum % k != 0) return false;
 6         int[] visited = new int[nums.length];
 7         return canPartition(nums, visited, 0, k, 0, 0, sum / k);
 8     }
 9 
10     public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target) {
11         if (k == 1) return true;
           if (cur_sum > target) return false;
12         if (cur_sum == target && cur_num > 0) return canPartition(nums, visited, 0, k - 1, 0, 0, target);
13         for (int i = start_index; i < nums.length; i++) {
14             if (visited[i] == 0) {
15                 visited[i] = 1;
16                 if (canPartition(nums, visited, i + 1, k, cur_sum + nums[i], cur_num++, target)) {
17                     return true;
18                 }
19                 visited[i] = 0;
20             }
21         }
22         return false;
23     }
24 }