Created
February 13, 2019 06:53
-
-
Save aarti/17eccdd82647e2446348ccf5e736c899 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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] | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment