[Question]: Given an integer array that may contain duplicates, find all possible subsets (the power set). No duplicates allowed in answer. Solution in any order allowed.
class Solution {
func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
guard nums.count > 0 else { return [] }
var output = [[Int]]()
var candidates = [Int]()
let startIndex = 0
let sorted = nums.sorted()
uniqueSet(&output, &candidates, startIndex, sorted)
return output
}
// This is kind of simillar to the "inorder traversal"
private func uniqueSet(_ output: inout [[Int]], _ candidates: inout [Int], _ startIndex: Int, _ nums: [Int]) {
//Entering valid values store each case("node")'s value
output.append(candidates)
// try to find if it has "children", if no "child", we done
for i in startIndex..<nums.count {
// filter out cases which may cause duplicate subsets
guard i == startIndex || nums[i] != nums[i - 1] else { continue }
// update candidates to next level's value(child's value)
candidates.append(nums[i])
// startIndex + 1, go next level(go to its child)
uniqueSet(&output, &candidates, i+1, nums)
// update candidates to previous level's value(parent's value)
candidates.removeLast()
}
}
}
// ex: [1, 2, 2]; assume it is like a tree(inorder traversal), "*" indicates duplicated case
// []
// / \ \
// [1] [2] [*2]
// / \ |
// [1, 2] [1, *2] [2, 2]
// /
// [1, 2, 2]
// output: [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]