package main

func combine(nums []int, k int) (res [][]int) {
	n := len(nums)
	if n == k || k == 0 {
		row := make([]int, k)
		for i := range row {
			row[i] = nums[i]
		}
		return append(res, row)
	}
	// C(k)(n) = C(k-1)(n-1) + C(k)(n-1)
	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
}

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

/* func main() {
	a1 := []int{1, 2, 3}
	fmt.Println(subsets(a1))
} */