package main import ( "fmt" "sort" ) func minInt(x, y int) int { if x < y { return x } return y } // Int2DSlice ... type Int2DSlice [][]int func (p Int2DSlice) Len() int { return len(p) } func (p Int2DSlice) Less(i, j int) bool { if len(p[i]) == 0 { return true } if len(p[j]) == 0 { return false } bound := minInt(len(p[i]), len(p[j])) fmt.Println(p[i][0], p[j][0], bound) for k := 0; k < bound; k++ { if p[i][k] < p[j][k] { return true } } return len(p[i]) == bound } func (p Int2DSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } func subsetsWithDupIter(nums []int, subsets [][]int, subsetsMap map[string]bool) [][]int { if len(nums) == 0 { return subsets } newSubsets := [][]int{} for _, set := range subsets { newSet := append(set, nums[0]) if _, ok := subsetsMap[fmt.Sprint(newSet)]; ok { continue } subsetsMap[fmt.Sprint(newSet)] = true newSubsets = append(newSubsets, newSet) } return subsetsWithDupIter(nums[1:], append(subsets, newSubsets...), subsetsMap) } func subsetsWithDup(nums []int) [][]int { sort.Ints(nums) subsets := [][]int{[]int{}} subsetsMap := make(map[string]bool, 0) result := subsetsWithDupIter(nums, subsets, subsetsMap) sort.Sort(Int2DSlice(result)) return result } func testSubsetsWithDup(nums []int) { subsets := subsetsWithDup(nums) fmt.Println("The subsets of", nums, "is", subsets) } func main() { nums := []int{1, 2, 1, 2} testSubsetsWithDup(nums) }