ac solution code


  • 0
    // Solution. DFS Recursive - time = O(n!); space = O(n) - path
    func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
        var res = [[Int]]()
        var path = [Int]()
        let nums = nums.sorted(by: <)// sort first
        dfs(nums, 0, &path, &res)
        return res
    }
    private func dfs(_ nums: [Int], _ start: Int, _ path: inout[Int], _ res: inout [[Int]]) {
        // (termination case)
        res.append(Array(path))// Add all possible Subsets to the result
        // As path only contains nums[0..start-1] elements, so impossible to contain nums[start..n-1], no need to check
        for i in start..<nums.count {
            if (i > start && nums[i] == nums[i - 1]) {// Avoid duplicated numbers
                continue
            }
            path.append(nums[i])
            dfs(nums, i + 1, &path, &res)// Next start should be i + 1
            path.removeLast()// Backtracking
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.