Java实现 LeetCode 698 划分为k个相等的子集(递归)

谁践踏了优雅 2023-07-23 05:00 26阅读 0赞

## 698. 划分为k个相等的子集 ##

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = \[4, 3, 2, 3, 5, 2, 1\], k = 4  
输出： True  
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

注意:

1 <= k <= len(nums) <= 16  
0 < nums\[i\] < 10000

class Solution { 
        
        int K = 0, N = 0;
        
        public boolean canPartitionKSubsets(int[] nums, int k) { 
    		int n = nums.length, sum = 0, eachSum = 0;
    		if (n == 0 || k == 0)
    			return false;
    		N = n;
    		K = k;
    		int[] arr = new int[k];
    		for (int i : nums)
    			sum += i;
    		if (sum % k != 0)
    			return false;
    		eachSum = sum / k;
    		Arrays.fill(arr, eachSum);
    		Arrays.sort(nums);
    		return helper(nums, n-1, arr);
    	}
    
    	boolean helper(int[] nums, int cur, int[] arr) { 
    		if (cur < 0)
    			return true;
    		int temp = nums[cur];
    		for (int i = 0; i < K; i++) { 
    			if (arr[i] == temp || (cur > 0 && arr[i] - temp >= nums[0])) { 
    				arr[i] -= temp;
    				if (helper(nums, cur - 1, arr)) { 
    					return true;
    				}
    				arr[i] += temp;
    			}
    		}
    		return false;
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，26人围观）

还没有评论，来说两句吧...

相关阅读

相关【力扣 leetcode】698：划分为k个相等的子集

每日进步剪枝：通过判断避免一些不必要的遍历过程。可行性剪枝：方案不可行时，回溯。最优性剪枝: 方案的解不可能优于当前

迷南。/ 2023年10月09日 14:46/ 0 赞/ 24 阅读

相关 LeetCode - 698 划分为k个相等的子集

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [698. 划分为k个相等的子集 - 力扣（

待我称王封你为后i/ 2023年09月23日 14:32/ 0 赞/ 92 阅读

相关 Java实现 LeetCode 698 划分为k个相等的子集(递归)

698. 划分为k个相等的子集给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。示例 1：输入： num

谁践踏了优雅/ 2023年07月23日 05:00/ 0 赞/ 27 阅读

相关递归实现整数划分

递归思想递归是算法设计中的一种基本而重要的算法。递归方法通过函数调用自身将问题转化为本质相同但规模较小的子问题，是分治策略的具体体现。不多废话，直接上故事 ->从前

「爱情、让人受尽委屈。」/ 2023年07月11日 08:50/ 0 赞/ 8 阅读

相关 lintcode588. 划分和相等的子集

给一只含有正整数的非空数组, 找到这个数组是否可以划分为两个元素和相等的子集。样例例1: 输入: nums = [1, 5,

清疚/ 2023年05月22日 08:56/ 0 赞/ 19 阅读

相关【递归】 LeetCode90. 子集 II

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

以你之姓@/ 2022年12月03日 05:21/ 0 赞/ 192 阅读

相关【递归】 LeetCode78. 子集

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

川长思鸟来/ 2022年12月03日 05:21/ 0 赞/ 226 阅读

相关 698 划分为k个相等的子集（dfs减枝）

1. 问题描述：给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。示例 1：输入： nums = \[4,

落日映苍穹つ/ 2022年09月03日 11:22/ 0 赞/ 115 阅读

相关 leetcode 698. Partition to K Equal Sum Subsets K个相等子集 + 深度优先搜索DFS

Given an array of integers nums and a positive integer k, find whether it’s possible to

男娘i/ 2022年06月03日 08:50/ 0 赞/ 153 阅读

相关【LeetCode】第698题：将一个整数数组划分为K个相等的子集问题（字节跳动面试题）

最近看面经，有人在字节跳动的面试中，手写这道题，但是发现是 LeetCode 上的原题，所以记录下来。 > 题目：给定一个整数数组 nums 和一个正整数 k，找出是否有可

今天药忘吃喽~/ 2021年12月14日 05:41/ 0 赞/ 225 阅读