_698划分为k个相等的子集 && _473火柴拼正方形 && _416分割等和子集

活动介绍
转眼又一年~~2023马上就要到尾声了，我们的年度征文如约而至！诚挚邀请你参与本次活动，与我们一起回顾过去这一年。

你可以分享的内容有：

印象深刻的实战经历
系统学习新技术的心得体会
精心整理的技术文档
想要安利给所有人的开发工具
对技术行业的深度思考
职业规划与心灵成长
新年Flag
在项目中取得的辉煌成绩
在应用开发中遇到的问题与解决方案
职场经历与升职感悟
编程语言的新趋势
我的最佳代码实践
我的最大收获与成长
我的技术发展规划
…
主题不限！期待你的参与~~

投稿方式
点击本页面底部的【发布文章】，方可成功参与活动！

征文时间
文章投稿：12月26日-1月21日
内部评审：1月22日-1月25日
榜单公布：1月25日
奖品寄送：2月5日前
征文奖品
奖品：CSDN实体铭牌（定制ID）+“算你厉害”定制奖牌+定制马克杯
评选规则：质量分（30%）+评论数（30%）+内部评审（40%）
人数：40人
奖品图片
专属铭牌在这里插入图片描述在这里插入图片描述

注意事项
严禁刷量！！！刷量行为一旦被核实，立即取消评选资格；
投稿文章需为公开的原创文，且要切合“年度征文”的主题，非相关主题、文章比较水、毕设、引流、抄袭、纯资讯、刷题等文章均不在评选范围内；
内部评审主要参考文章的内容完整度、主题贴合度、内容深度、整体排版等方面；
奖品将于榜单公布后七个工作日内寄送，在奖品寄送（2月5日）前，如果对上榜文章存疑，欢迎举报；
单人投稿多篇，只选取综合数据最高的一篇进入评选；
补充说明：博主本人的评论数不会计入“评论数”分值中。

_416分割等和子集

package 代码随想录.动态规划;

import java.util.Arrays;

public class _416分割等和子集 {
    /**
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        //给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
        int allSum = Arrays.stream(nums).sum();
        if (allSum % 2 != 0) {
            return false;
        }
        Arrays.sort(nums);
        int target = allSum / 2;
        int [] dp = new int[target + 1];
        for (int i = 0;i< nums.length;i++){
            for (int j = target;j>= nums[i];j--){
                //物品i的重量是nums[i],其价值也是nums[i]
                dp[j] = Math.max(dp[j],dp[j - nums[i]] + nums[i]);
            }
            //剪枝一下，每一次完成內層的for-loop，立即檢查是否dp[target] == target，優化時間複雜度（26ms -> 20ms）
            if (dp[target] == target){
                return true;
            }
        }
        return dp[target] == target;
    }
}

_473火柴拼正方形_状态压缩and动态规划

package 代码随想录.动态规划;

import java.util.Arrays;

public class _473火柴拼正方形_状态压缩and动态规划 {
    /**
     *
     * @param matchsticks
     * @return
     */
    public boolean makesquare(int[] matchsticks) {
        int allSum = Arrays.stream(matchsticks).sum();
        if (allSum % 4 != 0) {
            return false;
        }
        Arrays.sort(matchsticks);
        int len = allSum / 4 ;
        int n = matchsticks.length;
        int [] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int s = 1; s < (1 << n); s++) {
            for (int k = 0;k<n;k++){
                if ((s & (1 << k)) == 0){
                    continue;
                }
                int s1 = s & ~(1 << k);
                if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len){
                    dp[s] = (dp[s1] + matchsticks[k]) % len;
                    break;
                }
            }
        }
        return dp[(1<<n) -1] == 0;
    }
}

_473火柴拼正方形_回溯

package 代码随想录.动态规划;

import java.util.Arrays;

public class _473火柴拼正方形_回溯 {
    /**
     *
     * @param matchsticks
     * @return
     */
    public boolean makesquare(int[] matchsticks) {
        int allSum = Arrays.stream(matchsticks).sum();
        if (allSum % 4 != 0) {
            return false;
        }
        Arrays.sort(matchsticks);
        for (int i = 0,j = matchsticks.length-1; i < j; i++,j--) {
            int temp = matchsticks[i];
            matchsticks[i] = matchsticks[j];
            matchsticks[j] = temp;
        }
        int [] edges = new int[4];
        return dfs(0,matchsticks, edges,allSum / 4);
    }
    /**
     *
     * @param index
     * @param matchsticks
     * @param edges
     * @param average
     * @return
     */
    private boolean dfs(int index, int[] matchsticks, int[] edges, int average) {
        if (index == matchsticks.length){
            return true;
        }
        for (int i = 0;i<edges.length;i++){
            edges[i] += matchsticks[index];
            if (edges[i] <= average && dfs(index + 1 ,matchsticks,edges,average)){
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;
    }
}

_698划分为k个相等的子集_状态压缩and记忆化搜索

package 代码随想录.动态规划;

import java.util.Arrays;

public class _698划分为k个相等的子集_状态压缩and记忆化搜索 {
    private int [] nums;
    private int person,n;
    boolean [] dp;
    /**
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // TODO 将一个数组分解成，k个独立的子集合，并且这k个子集合数值大小均相等
        this.nums = nums;
        int allSum = Arrays.stream(nums).sum();
        if (allSum % k != 0) {  //如果不能k等分，则说明无法实现对应的要求
            return false;
        }
        person = allSum / k;    //算出每个人的均分获得值
        Arrays.sort(nums);
        n = nums.length;
        if (nums[n-1] > person){
            return false;
        }
        dp = new boolean[1 << n];   //1 <= k <= len(nums) <= 16
        Arrays.fill(dp,true);
        return dfs((1 << n) - 1,0);
    }
    /**
     *
     * @param s 我们可以用一个整数S来表示当前可用的数字集合
     * @param p 用到第几个元素
     * @return
     */
    private boolean dfs(int s , int p) {
        if (s == 0){
            return true;
        }
        if (!dp[s]){
            return dp[s];
        }
        dp[s] = false;
        for (int i = 0;i<n;i++){
            if (nums[i] + p > person){
                break;
            }
            if (((s >> i) & 1) != 0){
                if (dfs(s ^ (1 << i),(p + nums[i]) % person)){
                    return true;
                }
            }
        }
        return false;
    }
}

_698划分为k个相等的子集_状态压缩and动态规划

package 代码随想录.动态规划;

import java.util.Arrays;

public class _698划分为k个相等的子集_状态压缩and动态规划 {
    /**
     *
     * @param nums
     * @param k
     * @return
     */
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int allSum = Arrays.stream(nums).sum();
        if (allSum % k != 0) {  //如果不能k等分，则说明无法实现对应的要求
            return false;
        }
        int person = allSum / k;    //算出每个人的均分获得值
        Arrays.sort(nums);
        int n = nums.length;
        if (nums[n-1] > person) {
            return false;
        }
        boolean [] dp = new boolean[1 << n];   //1 <= k <= len(nums) <= 16
        int [] curSum = new int[1 << n];
        dp[0] = true;
        for (int i = 0;i < 1<<n;i++){
            if (!dp[i]){
                continue;
            }
            for (int j = 0;j < n;j++){
                if (curSum[i] + nums[j] > person){
                    break;
                }
                if (((i >> j) & 1) == 0){
                    int next = i | (1 << j);
                    if (!dp[next]){
                        curSum[next] = (curSum[i] + nums[j]) % person;
                        dp[next] = true;
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}