package main

import (
	"sort"
)

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	subsets := [][]int{[]int{}}
	for i, cnt := 0, 0; i < len(nums); i += cnt {
		for cnt = 1; cnt+i < len(nums) && nums[cnt+i] == nums[i]; cnt++ {
			// count the number of same elements
		}
		preLen := len(subsets)
		for j := 0; j < preLen; j++ {
			subset := make([]int, len(subsets[j]))
			copy(subset, subsets[j]) // deep copy, not create slice (!!!)
			for k := 0; k < cnt; k++ {
				subset = append(subset, nums[i])
				subsets = append(subsets, subset)
			}
		}
	}
	return subsets
}

// func main() {
// 	nums := []int{1, 2, 2, 3, 4}
// 	fmt.Println(subsetsWithDup(nums))
// }