# 698. Partition to K Equal Sum Subsets

Question link is here.

Given an integer array nums and an integer k, return true if it is 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.

Example 2:

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

# Solution

This a classic backtracking problem.

There are two key ideas here.

First, if we need to partition nums to K equal sum subsets, we must have $sum \% k == 0$ .

Second, two achieve optimal time complexity, we need to prun the backtracking times. Which means during backtracking, if a number is skiped in the current round, we don't need to consider it until the next round. What's more, sort the nums and starts from largest number can help the pruning, because if large increase in the sum change helps produces less branches.

Code is shown below.

class Solution {
    int[] nums = null;
    int k = 0;
    int target = 0;
    public boolean helper(int count, int sum, boolean[] visited, int index) {
        if(count == k - 1)
            return true;
        if(sum > target) 
            return false;
        if(sum == target) 
            return helper(count+1, 0, visited, nums.length-1);
        for(int i = index; i >= 0; i--) {
            if(!visited[i]){
                visited[i] = true;
                if(helper(count, sum + nums[i], visited, i-1)) {
                    return true;
                }
                visited[i] = false;
            }
        }    
        return false;       
    }
    
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        this.nums = nums;
        this.k =k;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(sum % k != 0)
            return false;
        target = sum / k;
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        return helper(0, 0, visited, nums.length-1);
    }
}

Time Complexity: $(k*2^N)$

Space Complexity: $O(N)$

Leetcode 698

Partition to K Equal Sum Subsets

# 698. Partition to K Equal Sum Subsets

# Solution