Leetcode - subsets && subsets-ii
https://leetcode.com/problems/subsets/
https://leetcode.com/problems/subsets-ii/
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
subset-ii is containing duplicate numbers in nums
func subsets(nums []int) [][]int {
result := [][]int{}
sort.Ints(nums)
backtrack(nums, &[]int{}, &result, 0)
return result
}
func backtrack(nums []int, tmpList *[]int, result *[][]int, start int) {
list := make([]int, len(*tmpList))
copy(list, *tmpList)
*result = append(*result, list)
for i := start; i < len(nums); i++ {
*tmpList = append(*tmpList, nums[i])
backtrack(nums, tmpList, result, i+1)
*tmpList = (*tmpList)[:len(*tmpList)-1]
}
}
func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
result := [][]int{}
backtrack(nums, &result, &[]int{}, 0)
return result
}
func backtrack(nums []int, result *[][]int, tmpList *[]int, start int) {
list := make([]int, len(*tmpList))
copy(list, *tmpList)
*result = append(*result, list)
for i := start; i < len(nums); i++ {
if i > start && nums[i] == nums[i-1] {
continue
}
*tmpList = append(*tmpList, nums[i])
backtrack(nums, result, tmpList, i+1)
*tmpList = (*tmpList)[:len(*tmpList)-1]
}
}
The only thing should be paid attention to is tmpList will be changed even if it's added to result set. So it requires another list to copy all elements in tmpList and store it
评论 (0)
