Partition of a set into K subsets with equal sum

Given an integer array of N elements, the task is to divide this array into K non-empty subsets such that the sum of elements 

in every subset is same. All elements of this array should be part of exactly one partition.
Examples:

Input : arr = [2, 1, 4, 5, 6], K = 3
Output : Yes
we can divide above array into 3 parts with equal
sum as [[2, 4], [1, 5], [6]]

Input  : arr = [2, 1, 5, 5, 6], K = 3
Output : No
It is not possible to divide above array into 3
parts with equal sum

input check, 正数？　　

In every recursion, we at most try k groups, which means the search tree has k branches at most. And the depth of the search tree is the max number of elements we can put in a group, which is N - k + 1. the time complexity is O(k^(n-k+1)) or O(k^(n-k))

 

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.

An corner case is when sum = 0, my method is to use cur_num to record the number of elements in the current subset. Only if cur_sum = sum/k && cur_num >0, we can start another look up process.

public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(int num:nums)sum += num;
        if(k <= 0 || sum%k != 0)return false;
        int[] visited = new int[nums.length];
        return canPartition(nums, visited, 0, k, 0, 0, sum/k);
    }
    
    public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target){
        if(k==1)return true;
        if(cur_sum == target && cur_num>0)return canPartition(nums, visited, 0, k-1, 0, 0, target);
        for(int i = start_index; i<nums.length; i++){
            if(visited[i] == 0){
                visited[i] = 1;
                if(canPartition(nums, visited, i+1, k, cur_sum + nums[i], cur_num++, target))return true;
                visited[i] = 0;
            }
        }
        return false;
    }

　　

返回其中一组解：

public void dfs(List<List<Integer>> ans, List<Integer> list, int[] nums, int k, int[] visited,  int count,int sum,int ave) {
        if (sum == ave && list.size() > 0) {
            ans.add(new ArrayList<>(list));
            if (count == k - 1) {
                a = true;
                return;
            }
            dfs(ans, new ArrayList<>(), nums, k, visited, count + 1, 0, ave);
        }
        if (sum > ave) {
            return;
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] + sum > ave || a == true) {
                    return;
                }
                if (visited[i] != 1) {
                    sum += nums[i];
                    visited[i] = 1;
                    list.add(nums[i]);
                    dfs(ans, list, nums, k, visited, count, sum, ave);
                    list.remove(list.size() - 1);
                    sum -= nums[i];
                    visited[i] = 0;
                }
            }
        }
    }