子集

1. 题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

2. 思路

1. 思路一
   • 跟全排列.md差不多
   • 区别在于全排列是长度达到len(num)才得到结果，而子集则是每次递归都得到结果

3. 实现

3.1. DFS

• 版本一

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
}

• 版本二

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. 参考

• 回溯算法 - 子集 - 力扣（LeetCode）