# Return all possible subset from an array

[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]]``````