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

Leave a Comment

Your email address will not be published. Required fields are marked *