generate_subsets.go

package main

import (
	"fmt"
	"math"
)

var cases = [][]int{
	[]int{},
	[]int{0},
	[]int{0, 1},
	[]int{0, 1, 2},
	[]int{0, 1, 2, 3},
	[]int{0, 1, 2, 3, 4},
}

// Write a function to return all subsets of a set
func main() {
	for _, c := range cases {
		fmt.Println(gen_recursive(c))
	}
	for _, c := range cases {
		fmt.Println(gen_iterative(c))
	}
}

// In the iterative case we work with binary property that an element is either in the set or not
// so all numbers could be represented from 0 up to 2^n
func gen_iterative(nums []int) [][]int {
	res := [][]int{}
	max := int(math.Pow(float64(2), float64(len(nums))))
	for i := 0; i < max; i++ {
		s := fmt.Sprintf("%0*b", len(nums), i) // binary number to the size of nums
		var ns []int
		// figure this out at some point, need to use the binary number as a bitset and
		// only include the elements that are needed in the set
		for k, c := range s {
			if c == '1' {
				ns = append(ns, nums[k])
			}
		}
		res = append(res, ns)
	}
	fmt.Printf("Size=%d ", len(res))
	return res
}

func gen_recursive(nums []int) [][]int {
	res := [][]int{}
	buffer := []int{} // this expands and contracts with the last set value as backtracking occurs
	start_index := 0
	backtrack(start_index, buffer, &res, nums)
	fmt.Printf("Size=%d ", len(res))
	return res
}

func backtrack(idx int, b []int, res *[][]int, nums []int) {
	// clone and store in res
	var e = make([]int, len(b))
	copy(e, b)
	*res = append(*res, e)

	// recursion base case in this case is when we cannot go in the loop
	// function will simply return
	for i := idx; i < len(nums); i++ {
		b = append(b, nums[i]) // add to buffer
		backtrack(i+1, b, res, nums)
		// The above backtrack should have fully expanded, so remove the last element
		// and continye with loop
		b = b[:len(b)-1]
	}
}