leetcode90: Subsets II

[carloscn]

Description

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

Input: nums = [0] Output: [[],[0]]

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10

[carloscn]

Analysis

我们拆成两个子问题，一个是列出元素所有的子数组，一个是去掉重复的数组。

• 列出子数组可以采用循环的方法
• 去掉重复的数组采用查找的方式

int32_t subsets_with_dup(int32_t *array, size_t len)
{
    int32_t ret = 0;

    if (array == NULL || 0 == len) {
        ret = -1;
        goto finish;
    }

    BUFLIST_T *buffer_list = NULL;
    BUFFER_T *buffer = NULL;

    buffer_list = buflist_malloc();
    UTILS_CHECK_PTR(buffer_list);

    buffer = buffer_malloc(BUFFER_DEFUALT_SIZE);
    UTILS_CHECK_PTR(buffer);

    // collect subset
    int32_t num = 0, i = 0, j = 0, k = 0, n = 0;

    num = 1 << len;
    for(i = 0; i < num; i ++) {
        j = i;
        k = 0;
        n = 0;

        while (j) {
            if (j & 1) {
                buffer_push_tail(buffer, array[k]);
            }
            j >>= 1;
            k ++;
        }
        ret = buflist_add(buffer_list, buffer);
        UTILS_CHECK_RET(ret);
        buffer_clear(buffer);
    }

    // set the bufferlist
    ret = buflist_set(buffer_list);
    UTILS_CHECK_RET(ret);

    // print buffer list
    buflist_infolog(buffer_list);

finish:
    buffer_free(buffer);
    buflist_free(buffer_list);
    return ret;
}

[carloscn]

code

https://review.gerrithub.io/c/carloscn/structstudy/+/556896 https://github.com/carloscn/structstudy/commit/f618322862fdcc7b5900af9135371c3ea964fe70