leetcode416：分割等和子集（partition_equal_subset_sum）

[carloscn]

问题描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2：

输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。   提示：

1 <= nums.length <= 200 1 <= nums[i] <= 100

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/partition-equal-subset-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[carloscn]

问题分析

一般思维：

分析过程：

• 分为1, n-1个元素： (1) + (2,3,3) / (2) + (1,3,5) / (3) + (1,2,5) / (4) + (1,2,3)
• 分为2, n-2个元素： (1,2) + (3, 5) / (1,3) + (2,5) / (1,5) + (2,3) / (2,3) + (1,5) / (2,5) + (1,3)
• 分为3, n-3个元素：与第一项一样。

因此这里的重点是关于子数组的遍历，我们不用递归而用循环遍历子数组，该方法应该被直接背下来。以下是遍历子数组的原语：

    num = 1 << len;
    for(i = 0; i < num; i ++) {
        j = i;
        k = 0;
        n = 0;
        while (j) {
            if (j & 1) {
                temp_buffer[n] = array[k];
                n ++;
            }
            j >>= 1;
            k ++;
        }
        utils_print_int64_array(temp_buffer, n, "sub: ");
    }

我们这道题的程序是：

int32_t partition_equal_subset_sum(const int64_t *array, size_t len, bool *res)
{
    int32_t ret = 0;
    BUFFER_T *a_sub_buffer = NULL;
    BUFFER_T *b_sub_buffer = NULL;
    size_t i, j, k, sub_num;

    UTILS_CHECK_PTR(array);
    UTILS_CHECK_LEN(len);
    UTILS_CHECK_PTR(res);

    a_sub_buffer = buffer_malloc(len);
    UTILS_CHECK_PTR(a_sub_buffer);

    b_sub_buffer = buffer_malloc(len);
    UTILS_CHECK_PTR(b_sub_buffer);

    sub_num = 1 << len;
    for (i = 0; i < sub_num; i ++) {
        j = i;
        k = 0;
        while (j) {
            if (j & 1) {
                ret = buffer_push_tail(a_sub_buffer, array[k]);
                UTILS_CHECK_RET(ret);
            }
            j >>= 1;
            k ++;
        }

        j = sub_num - i - 1;
        k = 0;
        while (j) {
            if (j & 1 == 1) {
                ret = buffer_push_tail(b_sub_buffer, array[k]);
                UTILS_CHECK_RET(ret);
            }
            j >>= 1;
            k ++;
        }

        if (buffer_sum(a_sub_buffer) == buffer_sum(b_sub_buffer)) {
            *res = true;
            printf("the a buffer is : "); buffer_print(a_sub_buffer);
            printf("the b buffer is : "); buffer_print(b_sub_buffer);
            goto finish;
        }
        buffer_clear(a_sub_buffer);
        buffer_clear(b_sub_buffer);
    }

finish:
    buffer_free(a_sub_buffer);
    buffer_free(b_sub_buffer);
    return ret;
}