package main

import (
	"fmt"
	"sort"
)

func combine(nums []int, k int) (res [][]int) {
	n := len(nums)
	if k == 0 || k == n {
		row := make([]int, k)
		for i := range row {
			row[i] = nums[i]
		}
		return append(res, row)
	}
	for _, row := range combine(nums[:n-1], k-1) {
		row = append(row, nums[n-1])
		res = append(res, row)
	}
	res = append(res, combine(nums[:n-1], k)...)
	return res
}

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	res := [][]int{}
	for i := 0; i <= len(nums); i++ {
		res = append(res, combine(nums, i)...)
	}
	return res
}

func main() {
	arr := []int{1, 3, 1}
	fmt.Println(subsetsWithDup(arr))
}