LeetCode [698] Partition to K Equal Sum Subsets

 698. Partition to K Equal Sum Subsets

Medium

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public boolean canPartitionKSubsets(int[] nums, int k) { int s = 0; for(int i:nums) s+=i; if(s%k!=0) return false; return helper(nums, new boolean[nums.length], 0, s/k, 0, k); } boolean helper(int[] nums, boolean[] visited, int curSum, int targetSum, int index, int k){ if(k==0) return true; if(curSum == targetSum){ return helper(nums, visited, 0, targetSum, 0, k-1); } for(int i=index; i<nums.length; ++i){ if(visited[i]==false && curSum+nums[i]<=targetSum){ visited[i] = true; if(helper(nums, visited, curSum+nums[i], targetSum, i+1, k)) return true; visited[i] = false; } } return false; } }