Description

Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

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

假设没有重复元素，每个元素有出现、不出现两种情况。

当有重复元素后，假设重复元素：[2, 2, 2]，对于元素2有不出现、出现一次[2]、出现两次[2, 2]、出现三次[2, 2, 2] 四种情况。

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

func subsetsWithDup(nums []int) [][]int {
    sort.Ints(nums)

    result := [][]int{[]int{}}

    for i := 0; i < len(nums); {
        curLen := len(result)

        // cout of this number
        count := 1
        for j := i + 1; j < len(nums) && nums[j] == nums[i]; j++ {
            count++
        }

        for idx := 0; idx < curLen; idx++ {
            for k := 1; k <= count; k++ {
                r := make([]int, len(result[idx]))
                copy(r, result[idx])

                // if the numver is visible
                // and if it's duplicate, eg. [2, 2, 2]
                // we can put in [2]、 [2, 2] or [2, 2, 2]
                for n := 0; n < k; n++ {
                    r = append(r, nums[i])
                }

                result = append(result, r)
            }
        }

        i += count
    }

    return result
}

Similar Problem