LeetCode: Subsets II

Posted on January 20, 2018July 26, 2020 by braindenny

Subsets II

Similar Problems:

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/subsets-ii
// Basic Ideas: dfs + backtracking
//
//  No need to use hashmap
//
// Complexity: Time O(pow(2, n)), Space O(pow(2, n))
import "sort"
func dfs(combination []int, nums []int, pos int, res *[][]int) {
    combination2 := make([]int, len(combination))
    copy(combination2, combination)
    *res = append(*res, combination2)

    for i:=pos; i<len(nums); i++ {
        if i>pos && nums[i] == nums[i-1] { continue }
        combination = append(combination, nums[i])
        dfs(combination, nums, i+1, res)
        combination = combination[0:len(combination)-1]
    }
}

func subsetsWithDup(nums []int) [][]int {
    res := [][]int{}
    sort.Ints(nums)
    dfs([]int{}, nums, 0, &res)
    return res
}

Post Views: 4