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 || len(p[j]) == 0 {
		return len(p[i]) == 0
	}
	bound := minInt(len(p[i]), len(p[j]))
	for k := 0; k < bound; k++ {
		if p[i][k] != p[j][k] {
			return p[i][k] < p[j][k]
		}
	}
	return len(p[i]) < len(p[j])
}
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))
	fmt.Println(subsetsMap)
	return result
}

func testSubsetsWithDup(nums []int) {
	subsets := subsetsWithDup(nums)
	fmt.Println("\nThe subsets of", nums, "is", subsets)
}

func main() {
	nums := []int{1, 2, 2, 1, 2, 3, 5, 7, 2}
	testSubsetsWithDup(nums)
}