题解 | #划分等和序列#

import java.util.*;

/**
 * NC385 划分等和序列
 * @author d3y1
 */
public class Solution {
    private boolean[] visited;
    private int avg;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型ArrayList
     * @param k int整型
     * @return bool布尔型
     */
    public boolean candivide (ArrayList<Integer> nums, int k) {
        return solution1(nums, k);
        // return solution2(nums, k);
    }

    /**
     * 动态规划: 01背包
     *
     * dp[j]表示背包大小为j时能够组成的最大的和(数组中的元素和)[数组中每个元素仅用一次]
     *
     * dp[j] = Math.max(dp[j], dp[j-num] + num)
     *
     * @param nums
     * @param k
     * @return
     */
    private boolean solution1(ArrayList<Integer> nums, int k){
        int n = nums.size();

        int sum = 0;
        for(int i=0; i<n; i++){
            sum += nums.get(i);
        }

        if(sum%k != 0){
            return false;
        }
        avg = sum/k;

        int[] dp = new int[sum+1];
        int num;
        for(int i=0; i<n; i++){
            num = nums.get(i);
            if(num > avg){
                return false;
            }
            // 数组中每个元素仅用一次 -> 降序
            for(int j=sum; j>=num; j--){
                dp[j] = Math.max(dp[j], dp[j-num] + num);
            }
        }

        // avg的倍数 均要判断
        for(int i=1; i<=k; i++){
            // 恰好装满 -> 恰好组成下一个元素和avg
            if(dp[avg*i] != avg*i){
                return false;
            }
        }

        return true;
    }

    /**
     * dfs: 遍历解空间
     * @param nums
     * @param k
     * @return
     */
    private boolean solution2(ArrayList<Integer> nums, int k){
        int n = nums.size();
        visited = new boolean[n];

        int sum = 0;
        for(int i=0; i<n; i++){
            sum += nums.get(i);
        }

        if(sum%k != 0){
            return false;
        }
        int avg = sum/k;

        return dfs(nums, k, avg);
    }

    /**
     * dfs: 递归
     * @param nums
     * @param k
     * @param target
     * @return
     */
    private boolean dfs(ArrayList<Integer> nums, int k, int target){
        if(k == 0){
            return true;
        }
        if(target == 0){
            if(dfs(nums, k-1, avg)){
                return true;
            }
        }else if(target < 0){
            return false;
        }else{
            for(int i=0; i<nums.size(); i++){
                if(!visited[i]){
                    visited[i] = true;
                    if(dfs(nums, k, target-nums.get(i))){
                        return true;
                    }
                    visited[i] = false;
                }
            }
        }

        return false;
    }
}