【LeetCode】90. 子集 II(错题2刷)

【LeetCode】90. 子集 II(错题2刷)

  • 思路
    难点在于可能包含重复元素,因此对于同层的元素(同一位置),不能出现同样的数字,否则就会重复,而不同层可以出现重复数字。
func subsetsWithDup(nums []int) [][]int {
    res := [][]int{}
    cur := []int{}
    used := make([]bool, len(nums))

    var backtracking func([]int, int)
    backtracking = func(nums []int, start int) {
        temp := make([]int, len(cur))
        copy(temp, cur)
        res = append(res, temp)

        for i := start; i < len(nums); i++ {
            if i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false {
                continue
            } else {
                cur = append(cur, nums[i])
                used[i] = true
                backtracking(nums, i + 1)
                cur = cur[: len(cur) - 1]
                used[i] = false
            }
        }
    }

    sort.Ints(nums)
    backtracking(nums, 0)
    return res
}

【LeetCode】90. 子集 II(错题2刷)

上一篇:【二叉树】leetcode662.二叉树最大宽度


下一篇:【代码随想录】第10章 贪心算法