关于算法:力扣划分为k个相等的子集

42次阅读

共计 1530 个字符,预计需要花费 4 分钟才能阅读完成。

一、题目:

给定一个整数数组  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

二、思路:

首先是题意:做每道算法题,最重要的是,读懂题意,从剖析咱们能够得进去的是,目标值及每个子集的和 target=sum(nums)/k, 所以就确定了目标值 target。
得出目标值后,咱们能够失去一些肯定为 false 的状况,如

  1. 目标值不为整数
  2. nums 中有值大于 target 的

咱们还能够先找出 nums 中是否有等于 target 的值,
这道题的思路就是把 nums 所有元素都放进长度为 k 的 groups 数组 当中,如果刚刚放完,则返回 true。
对于放进 groups 这个动作咱们称它为搜寻元素放进 group,对于一共 k 个子集的咱们只须要一个 for 循环就能解决。
应用递归咱们能够做到始终搜寻。只用扭转以后搜寻的值,就能始终向 group 数组中增加。
如果看不懂思路,请联合代码剖析。

三、代码:

public class 划分为 k 个相等的子集 {public static void main(String[] args) {划分为 k 个相等的子集 a = new 划分为 k 个相等的子集();
        int[] nums = {4, 3, 2, 3, 5, 2, 1};
        System.out.println(a.canPartitionKSubsets(nums,4));
    }

    public boolean canPartitionKSubsets(int[] nums, int k) {int sum = Arrays.stream(nums).sum();
        if (sum % k > 0) return false;
        // 由题意咱们能够晓得目标值相对是 sum/k
        int target = sum / k;
        // 给 nums 数组排序,递增程序
        Arrays.sort(nums);
        int row = nums.length - 1;
        // 如果最大的值大于目标值,则改数组必定不满足条件,间接返回 false
        if (nums[row] > target) return false;
        // 如果有等于目标值的,k--,row--
        while (row >= 0 && nums[row] == target) {
            row--;
            k--;
        }
        return search(new int[k], row, nums, target);
    }


    // 函数作用:搜寻 nums 中的每一个数,能不能增加到 groups 里,并且和等于 target,row 代表以后增加到 groups 中的数
    public boolean search(int[] groups, int row, int[] nums, int target) {
        // 如果 nums 中没有数了,则代表所有数全副放入 groups 中
        if (row < 0) return true;
        // 留神 row--,先赋值,再 --
        int v = nums[row--];
        // 遍历 groups 的 k 个子集
        for (int i = 0; i < groups.length; i++) {if (groups[i] + v <= target) {groups[i] += v;
                if (search(groups, row, nums, target)) return true;
                // 不能增加到 groups 中,则把它减去,及回溯
                groups[i] -= v;
            }
            // 如果遍历完了,所有数都不能放进 groups 中,及没有值相加或者自身等于 target,则跳出循环 break, 或者 return false;
            if (groups[i] == 0) return false;
        }
        return false;
    }
}

正文完
 0