Swift 3 Iterative and DFS methods


  • 1
    Y
    // iterative 16ms 100%
        func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
            var ans = [[Int]]()
            ans.append([Int]())
            var sorted = nums.sorted()
            var size = ans.count
            for i in 0..<sorted.count {
                let start = (i > 0 && sorted[i] == sorted[i - 1]) ? size : 0
                size = ans.count
                var temp = [[Int]]()
                for j in start..<ans.count {
                    var arr = ans[j]
                    arr.append(sorted[i])
                    temp.append(arr)
                }
                ans += temp
            }
            return ans
        }
        
    
        // dfs 100% 19ms
        func subsetsWithDup(_ nums: [Int]) -> [[Int]] {
            var ans = [[Int]]()
            backtracking(nums.sorted(), 0, [Int](), &ans)
            return ans
        }
        
        
        func backtracking(_ nums: [Int], _ start: Int, _ arr: [Int], _ ans: inout [[Int]]) {
            ans.append(arr)
            
            for i in start..<nums.count {
                if i > start && nums[i] == nums[i - 1] {
                    continue
                }
                var temp = arr
                temp.append(nums[i])
                backtracking(nums, i + 1, temp, &ans)
            }
        }
    
    
    

Log in to reply
 

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