LeetCode Problem 47-Permutations II

Posted on | In | Visitors

全排列 II。给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路一

回溯法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(result, tmp, nums, used):
            if len(tmp) == len(nums):
                result.append(tmp)
                return
            for i in range(len(nums)):
                if used[i]:
                    continue
                if i > 0 and nums[i] == nums[i-1] and used[i-1]:
                    return
                used[i] = True
                backtrack(result, tmp+[nums[i]], nums, used)
                used[i] = False
        result = []
        nums.sort()
        backtrack(result, [], nums, [False] * len(nums))
        return result

相似问题

  1. Next Permutation
  2. Permutations
  3. Palindrome Permutation II
  4. Number of Squareful Arrays
此时不赞何时赞！