Subset check with integer slices in Go

I am looking for a efficient way to check if a slice is a subset of another. I could simply iterate over them to check, but I feel there has to be a better way.

E.g.

> {1, 2, 3} is a subset of {1, 2, 3, 4}
> {1, 2, 2} is NOT a subset of {1, 2, 3, 4}

What is the best way to do this efficiently?

Thanks!

I think the most common way to solve a subset problem is via a map.

package main

import "fmt"

// subset returns true if the first array is completely
// contained in the second array. There must be at least
// the same number of duplicate values in second as there
// are in first.
func subset(first, second []int) bool {
	set := make(map[int]int)
	for _, value := range second {
		set[value] += 1
	}

	for _, value := range first {
		if count, found := set[value]; !found {
			return false
		} else if count < 1 {
			return false
		} else {
			set[value] = count - 1
		}
	}

	return true
}

func main() {
	fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4}))
	fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
}

The ability to check duplicate values is relatively uncommon. The code above solves the problem as asked (see: http://play.golang.org/p/4_7Oh-fgDQ) though. If you plan on having duplicate values, you'll have to keep a count like the code above does. If there will not be duplicate values, you can solve the problem more compactly by using a boolean for the map value instead of an integer.

If your slices are sorted, this does the job.

package main

import "fmt"

// Subset return whether a is a sublist of b. Both a and b must be (weakly) ascending.
func Subset(a, b []int) bool {
	for len(a) > 0 {
		switch {
		case len(b) == 0:
			return false
		case a[0] == b[0]:
			a = a[1:]
			b = b[1:]
		case a[0] < b[0]:
			return false
		case a[0] > b[0]:
			b = b[1:]
		}
	}
	return true
}

func main() {
	cases := []struct {
		a, b []int
		want bool
	}{
		{[]int{1, 2, 3}, []int{1, 2, 3, 4}, true},
		{[]int{1, 2, 2}, []int{1, 2, 3, 4}, false},
	}
	for _, c := range cases {
		if Subset(c.a, c.b) != c.want {
			fmt.Printf("Subset(%v, %v) = %v, want %v\n", c.a, c.b, Subset(c.a, c.b), c.want)
		}
	}
}

Algorithm to check if an array is a subset of another array in golang

package main

import "fmt"

func compare(arr1 []int, arr2 []int) bool {
	for _, num1 := range arr2 {
		status := false
		for _, num2 := range arr1 {
			if num1 == num2 {
				status = true
				break
			}
		}
		if !status {
			return false
		}
	}
	return true
}
func main() {
	arr1 := []int{1, 2, 3, 4, 5}
	arr2 := []int{1, 2, 3}
	if compare(arr1, arr2) {
		fmt.Println("arr2 is subset of arr1")
	} else {
		fmt.Println("arr2 is not subset of arr1")
	}
}