Subsets

1. Problem Description

Given an integer array nums whose elements are all distinct, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. You may return the solution in any order.

2. Approach

1. Approach 1
   • Similar to Permutations
   • The difference is that permutations produce a result only when the length reaches len(num), while subsets produce a result at every recursive call

3. Implementation

3.1. DFS

• Version 1

package main

import (
	"reflect"
	"sort"
)

func subsets(nums []int) [][]int {
	allPaths := make([][]int, 0)
	for i := 0; i <= len(nums); i++ {
		path := make([]int, 0)
		subsetDFS(nums, i, 0, &path, &allPaths)
	}

	res := make([][]int, 0)

	for _, path := range allPaths {
		if !inList3(res, path) {
			res = append(res, path)
		}
	}

	return res
}

func inList3(res [][]int, path []int) bool {
	for _, p := range res {
		if reflect.DeepEqual(p, path) {
			return true
		}
	}

	return false
}

func subsetDFS(nums []int, length int, index int, path *[]int, allPaths *[][]int) {
	if index == length {
		dst := make([]int, len(*path))
		copy(dst, *path)
		sort.Ints(dst)
		*allPaths = append(*allPaths, dst)
		return
	}

	for i := 0; i < len(nums); i++ {
		if !inList2(*path, nums[i]) {
			*path = append(*path, nums[i])
			subsetDFS(nums, length, index+1, path, allPaths)
			*path = (*path)[:len(*path)-1]
		}
	}
}

func inList2(path []int, num int) bool {
	for _, n := range path {
		if n == num {
			return true
		}
	}

	return false
}

• Version 2

func subsets(nums []int) [][]int {
    path := make([]int, 0)
    allPaths := make([][]int, 0)
    subsetsDFS(nums, 0, &path, &allPaths)
    return allPaths
}

func subsetsDFS(nums []int, index int, path *[]int, allPaths *[][]int) {
    dst := make([]int, len(*path))
    copy(dst, *path)
    *allPaths = append(*allPaths, dst)

    for i := index; i < len(nums); i++ {
        *path = append(*path, nums[i])
        subsetsDFS(nums, i+1, path, allPaths)
        *path = (*path)[:len(*path)-1]
    }
}

4. References

• Backtracking Algorithm - Subsets - LeetCode