Swift solution - Backtracking, Bit Manipulation


  • 1
    class Solution {
        func subsets_Backtracking(_ nums: [Int]) -> [[Int]] {
            var result = [[Int]]()
            var candidate = [Int]()
            
            backtracking(&result, &candidate, nums.sorted(), 0)
            
            return result
        }
        
        private func backtracking(_ result: inout [[Int]], _ candidate: inout [Int], _ nums: [Int], _ start: Int) {
            result.append(candidate)
            for i in start..<nums.count {
                candidate.append(nums[i])
                backtracking(&result, &candidate, nums, i + 1)
                candidate.removeLast()
            }
        }
    
        func subsets_BitManipulation(_ nums: [Int]) -> [[Int]] {
            let nums = nums.sorted()
            let n = nums.count
            let subsetCount = 1 << n
            var result = [[Int]](repeatElement([Int](), count: subsetCount))
            
            for i in 0..<n {
                for j in 0..<subsetCount {
                    if (j >> i ) & 1 != 0 {
                        result[j].append(nums[i])
                    }
                }
            }
            
            return result
        }
    }
    

Log in to reply
 

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