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

Categories:

题目描述
思路分析
1. 解法一：回溯 + 剪枝（推荐）
相似题目

题目描述

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

思路分析

解法一：回溯 + 剪枝（推荐）

核心思路：

先判断总和能否被 k 整除，目标子集和为 target。

将数组降序排序，优先放置大数以减少分支。

回溯将元素放入当前桶，桶满则开始下一个桶。

复杂度分析：

时间复杂度：O(n * 2^n)，其中 n 表示数组长度。

空间复杂度：O(n)，递归栈与标记数组占用线性空间。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int v : nums) {
            sum += v;
        }
        if (sum % k != 0) {
            return false;
        }

        int target = sum / k;
        Arrays.sort(nums);
        int n = nums.length;
        boolean[] used = new boolean[n];

        // 降序更快剪枝
        reverse(nums);
        return backtrack(nums, used, k, 0, 0, target);
    }

    private boolean backtrack(int[] nums, boolean[] used, int k, int start, int cur, int target) {
        if (k == 1) {
            return true;
        }
        if (cur == target) {
            return backtrack(nums, used, k - 1, 0, 0, target);
        }

        int prev = -1;
        for (int i = start; i < nums.length; i++) {
            if (used[i] || cur + nums[i] > target || nums[i] == prev) {
                continue;
            }

            used[i] = true;
            if (backtrack(nums, used, k, i + 1, cur + nums[i], target)) {
                return true;
            }
            used[i] = false;

            // 剪枝：同一层相同值只尝试一次
            prev = nums[i];
            if (cur == 0) {
                break;
            }
        }

        return false;
    }

    private void reverse(int[] nums) {
        for (int l = 0, r = nums.length - 1; l < r; l++, r--) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }
    }
}

func canPartitionKSubsets(nums []int, k int) bool {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if sum%k != 0 {
		return false
	}

	target := sum / k
	sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] })
	used := make([]bool, len(nums))

	var backtrack func(start int, k int, cur int) bool
	backtrack = func(start int, k int, cur int) bool {
		if k == 1 {
			return true
		}
		if cur == target {
			return backtrack(0, k-1, 0)
		}

		prev := -1
		for i := start; i < len(nums); i++ {
			if used[i] || cur+nums[i] > target || nums[i] == prev {
				continue
			}

			used[i] = true
			if backtrack(i+1, k, cur+nums[i]) {
				return true
			}
			used[i] = false

			// 剪枝：同一层相同值只尝试一次
			prev = nums[i]
			if cur == 0 {
				break
			}
		}

		return false
	}

	return backtrack(0, k, 0)
}

相似题目

题目	难度	考察点
416. 分割等和子集	中等	背包
473. 火柴拼正方形	中等	回溯
698. 划分为k个相等的子集	中等	回溯
943. 最短超级串	困难	状压 DP
996. 正方形数组的数目	困难	回溯

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/87907170