Java实现 LeetCode 698 划分为k个相等的子集(递归)
2023-09-14 08:58:02 时间
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;
}
}
相关文章
- (八)java垃圾回收和收尾
- Java实现 LeetCode 779 第K个语法符号(递归)
- Java实现 LeetCode 765 情侣牵手(并查集 || 暴力)
- Java实现 LeetCode 753 破解保险箱(递归)
- Java实现 LeetCode 736 Lisp 语法解析(递归)
- Java实现 LeetCode 726 原子的数量(递归+HashMap处理)
- Java实现 LeetCode 687 最长同值路径(递归)
- Java实现 LeetCode 679 24 点游戏(递归)
- Java实现 LeetCode 662 二叉树最大宽度(递归)
- Java实现 LeetCode 662 二叉树最大宽度(递归)
- Java实现 LeetCode 659 分割数组为连续子序列 (哈希)
- Java实现 LeetCode 650 只有两个键的键盘(递归 || 数学)
- Java实现 LeetCode 546 移除盒子(递归,vivo秋招)
- Java实现 LeetCode 529 扫雷游戏(DFS)
- Java实现 LeetCode 521 最长特殊序列 Ⅰ(出题人:“就是喜欢看你们不敢相信那么简单,又不敢提交的样子。”)...
- Java实现 LeetCode 494 目标和
- Java实现 LeetCode 407 接雨水 II(二)
- Java实现 LeetCode 372 超级次方
- Java实现 LeetCode 373 查找和最小的K对数字
- Java实现 LeetCode 335 路径交叉
- Java实现 LeetCode 303 区域和检索 - 数组不可变
- Java实现 LeetCode 106 从中序与后序遍历序列构造二叉树
- Java实现 LeetCode 84 柱状图中最大得矩形
- Java实现 LeetCode 48 旋转图像
- Java实现 LeetCode 23 合并K个排序链表
- Java实现合并排序
- 深入理解Java虚拟机(一)
- 使用Java代码连接SAP ABAP Netweaver服务器
- JUC学习之Java 线程常用方法
- idea创建Java项目