698. Partition to K Equal Sum Subsets

Link

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.

Solution

DFS+Backtracking

 public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum%k != 0) return false;
        sum = sum/k;
        
        boolean[] isUsed = new boolean[nums.length];
        return dfs(nums, isUsed, 0, sum, k, 0);
        
    }
    
    public boolean dfs(int[] nums, boolean[] isUsed, int index, 
                       int target, int time, int curSum){
        if(time == 1){
           return true; 
        }
        if(curSum == target){
            return dfs(nums, isUsed, 0, target, time-1, 0);
        }
        for(int i = index; i < nums.length; i++){
            if(isUsed[i] == false && nums[i] + curSum <= target){
                isUsed[i] = true;
                if(dfs(nums, isUsed, index+1, target, time, curSum+nums[i])) return true;
                isUsed[i] = false;
            }
        }
        return false;
    }