划分等和序列

public boolean candivide (ArrayList<Integer> nums, int k) {
    int sum = 0;
    for (Integer num : nums) {
        sum += num;
    }
    if (sum % k != 0) {
        return false;
    }
    int target = sum / k;
    int[] dp = new int[target + 1];
    for (Integer num : nums) {
        if (num > target) {
            return false;
        }
        for (int j = target; j >= num; j--) {
            dp[j] = Math.max(dp[j], dp[j - num] + num);
        }
        //我题目理解的有问题，还是案例不够多呀
        //nums = 2,6,3,10,8,4 k = 3时 不能凑出都是11的吧 但是还是返回的true
        if(dp[target] == target){
            return true;
        }
    }
    return false;
}

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @param k int整型
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/89ceab10d36140ce8f0d38c56e417f02?tpId=196&tqId=40516&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        1. 边界考虑：
            设nums的长度为n，所有元素和为sum，最大值为maxNum，target = sum / k
            a）如果n < k，无法分割，返回False
            b）如果sum % k != 0，无法分割，返回False
            c) 如果maxNum > target，无法分割，返回False
        2. 回溯函数dfs(k, target)表示当前剩余分割的序列数为k，当前分割区间剩余匹配的目标值为target
            若k == 0，说明分割成功，返回True
            若target == 0，需要分割的区间数-1，继续递归
            枚举当前可选的有效元素，标记为已访问，继续递归；回溯
    复杂度：
        时间复杂度：？？？
        空间复杂度：O(n)
    """

    def candivide(self, nums, k):
        # write code here
        def dfs(k, remain):
            if k == 0: # 分割序列成功
                return True
            if remain == 0: #
                if dfs(k - 1, target):
                    return True
            for i in range(n):
                if nums[i] > remain&nbs***bsp;visited[i]:  # 当前元素大于剩余匹配值 或者 已被选取
                    continue
                visited[i] = True
                if dfs(k, remain - nums[i]):
                    return True
                visited[i] = False
            return False

        n, Sum = len(nums), sum(nums)
        if n < k&nbs***bsp;Sum % k != 0:
            return False

        nums.sort(reverse=True)
        target = Sum / k
        if nums[0] > target:
            return False

        visited = [False] * n

        return dfs(k, target)


if __name__ == "__main__":
    sol = Solution()

    # nums, k = [5, 1, 3, 2, 4], 3

    nums, k = [5, 1, 4, 2, 3, 2], 3

    res = sol.candivide(nums, k)

    print res

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return bool布尔型
     */
    #include <vector>
    bool candivide(vector<int>& nums, int k) {
        // write code here    
        int sum=0;
        for(auto& n:nums) sum+=n;
        if(sum%k!=0) return false;
        sort(nums.rbegin(),nums.rend());
        int target=sum/k;
        vector<int> buckets(k,target);
        return dfs(nums,buckets,0);
    }
    
    bool dfs(vector<int>& nums,vector<int>& buckets,int index){
        if(index>=nums.size()) return true;
        for(int i=0;i<buckets.size();i++){
            if(nums[index]>buckets[i]) continue;
            if(i>0&&buckets[i]==buckets[i-1]) continue;
            buckets[i]-=nums[index];
            if(dfs(nums,buckets,index+1)) return true;
            buckets[i]+=nums[index];
        }
        return false;
    }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @param k int整型 
     * @return bool布尔型
     */
    int originTarget = 0;

    public boolean candivide(ArrayList<Integer> nums, int k) {
        // write code here
        int max = 0;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums.get(i);
            if (nums.get(i) > max) {
                max = nums.get(i);
            }
        }
        if (sum % k != 0) {
            return false;
        }
        // 一个和是多少
        originTarget = sum / k;
        // 最大的大于一个和，肯定不行
        if (max > originTarget) {
            return false;
        }
        // visited数组，标记已访问元素
        boolean[] visited = new boolean[nums.size()];
        return cal(nums, originTarget, visited, k);
    }

    private boolean cal(ArrayList<Integer> nums, int target, boolean[] visited, int k) {
        if (k == 0) {
            return true;
        }
        if (target < 0) {
            return false;
        } else if (target == 0) {
            // 递归k-1，继续访问
            return cal(nums, originTarget, visited, k - 1);
        }
        // target大于0，可以继续回溯
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) > target) {
                continue;
            }
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            boolean cal = cal(nums, target - nums.get(i), visited, k);
            if (cal) {
                return true;
            }
            visited[i] = false;
        }
        return false;
    }
}