go语言刷题：90. 子集 II

申明：本文只用做自己的学习记录

题目

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

代码

import "sort"

func subsetsWithDup(nums []int) [][]int {
	//初始化所需的变量值
	results := [][]int{}
	temp := []int{}
	start := 0
    // 对切片进行从小到大排序
    sort.Ints(nums)
    isvisited := make([]bool, len(nums))
	// 列出特殊情况
	if nums == nil || len(nums) == 0 {
		return results
	}
	BackTrack(isvisited, start, nums, temp, &results)
	return results
}

func BackTrack(isvisited []bool, start int, nums []int, temp []int, results *[][]int) {
	//将遍历的情况依次放进切片中
	current := make([]int, len(temp))
	copy(current, temp)
	*results = append(*results, current)

	//进行循环
	for i := start; i < len(nums); i++ {
        //减枝，将重复数字的支路剪掉
        if i > 0 && nums[i] == nums[i-1] && isvisited[i-1] == false {
            continue
        }
		//进行元素添加
		temp = append(temp, nums[i])
        isvisited[i] = true
		//回溯函数
		BackTrack(isvisited, i+1, nums, temp, results)
		//恢复到之前的状态
		temp = temp[:len(temp)-1]
        isvisited[i] = false
	}
}