90. Subsets II

罗列出一个包含重复数字的集合的所有的子集

思路： dfs, 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 6 star, dfs, 多练习
        # 先排序，然后dfs, 注意不能重复
        nums.sort()
        rs = []
        self.dfs([], rs, 0, nums)
        return rs


    def dfs(self, path, rs, start, nums):
        if len(path) <= len(nums) and path not in rs:
            rs.append(path)
        for i in range(start, len(nums)):
            self.dfs(path+[nums[i]], rs, i+1, nums)

Go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	ret := [][]int{}
	retP := &ret
	dfs(retP, nums, []int{}, 0)
	return *retP


}

func dfs(retP *[][]int, nums []int, path []int, start int) {
	temp := make([]int, len(path))
	copy(temp, path)
	*retP = append(*retP, temp)
	if len(nums) == 0 {return}
	for i:= start; i<len(nums); i++ {
		//fmt.Println(start, path)
		if i == start || nums[i] != nums[i-1] {  //注意去除重复
			dfs(retP, nums, append(path, nums[i]), i+1)
		}

	}
}