LeetCode 47. Permutations II

题目

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]  
Output:  
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路

跟permutation 1 差不多,只不过多了一个去重(或避免重复)的逻辑。 先把nums sort一遍,然后如果这个数和前面的数一样的话,其实就没有必要iterate, 可以跳过。

Swift 题解

func permuteUnique(_ nums: [Int]) -> [[Int]] {  
        var result = [[Int]]()

        let current = [Int]()
        var dict = [String: Bool]()

        helper(current: current, left: nums.sorted(), index: 0, dict: &dict, result: &result)

        return result
    }

    func helper(current: [Int], left: [Int], index: Int, dict: inout [String: Bool], result: inout [[Int]]) {
        if left.isEmpty {
            result.append(current)
            return
        }

        for (cIndex, value) in left.enumerated() {
            if cIndex > 0 && left[cIndex - 1] == left[cIndex] {
                continue
            }
            var next = current
            next.append(value)
            var copy = left
            copy.remove(at: cIndex)
            helper(current: next, left: copy, index: index + 1, dict: &dict, result: &result)
        }
    }

chenbo

编程爱好者

Singapore