组合类DFS

摘要

组合类搜索的隐式图模型
组合类搜索的时间复杂度和适用条件
如何对搜索结果进行去重
- 选代表vs哈希表

17 · 子集

给定一个含不同整数的集合，返回其所有的子集（任意顺序）。

时间复杂度 O (2^n)：

version 1

             []
        /           \
      [1]            []
    /    \         /    \   
   [1,2]  [1]    [2]     []

/**
 * @param nums: A set of numbers
 * @return: A list of lists
 *          we will sort your return value in output
 */
func Subsets(nums []int) [][]int {
	sorted := append([]int{}, nums...)
	sort.Ints(sorted)
	res := new([][]int)
	dfs(sorted, 0, []int{}, res)
	return *res
}

// 1. 递归的定义
func dfs(nums []int,
	index int,
	subset []int,
	res *[][]int) {

	// 3. 递归的出口
	if index == len(nums) {
		*res = append(*res, append([]int{}, subset...))
		return
	}

	// 2. 递归的拆解
	// 不选 nums[index]
	dfs(nums, index+1, subset, res)

	// 选 nums[index]
	subset = append(subset, nums[index])
	dfs(nums, index+1, subset, res)
}

version 2

           [ ]
     /      |      \
   [1]     [2]     [3]
 /    \            
[1,2]  [1,3] 
/
[1,2,3]

func Subsets2(nums []int) [][]int {
	sorted := append([]int{}, nums...)
	sort.Ints(sorted)
	res := new([][]int)
	dfs2(sorted, 0, []int{}, res)
	return *res
}

func dfs2(nums []int, index int, subset []int, res *[][]int) {
	*res = append(*res, append([]int{}, subset...))
	for i := index; i < len(nums); i++ {
		// dfs2(nums, i+1, append(subset, nums[i]), res)

		subset = append(subset, nums[i])
		dfs2(nums, i+1, subset, res)
		subset = subset[:len(subset)-1]
	}
}

18 · 子集 II

给定一个可能具有重复数字的列表，返回其所有可能的子集。

/**
 * @param nums: A set of numbers.
 * @return: A list of lists. All valid subsets.
 *          we will sort your return value in output
 */
func SubsetsWithDup(nums []int) [][]int {
	sorted := append([]int{}, nums...)
	sort.Ints(sorted)
	res := new([][]int)
	dfsWithDup(sorted, 0, []int{}, res)
	return *res
}

func dfsWithDup(nums []int, index int, subset []int, res *[][]int) {
	*res = append(*res, append([]int{}, subset...))
	for i := index; i < len(nums); i++ {
		if i != index && nums[i] == nums[i-1] {
			continue
		}
		subset = append(subset, nums[i])
		dfsWithDup(nums, i+1, subset, res)
		subset = subset[:len(subset)-1]
	}
}

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。