文章目錄

• • 1. 題目信息
  • 2. 解題

1. 題目信息

給定一個(gè)可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。

示例:輸入: [1,1,2] 輸出: [[1,1,2],[1,2,1],[2,1,1] ]

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/permutations-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

在leetcode46的基礎(chǔ)上做修改
類似題目：
LeetCode 491. 遞增子序列（回溯+判重）
LeetCode 996. 正方形數(shù)組的數(shù)目（回溯+剪枝）

• 先對數(shù)組排序
• 如果前一個(gè)數(shù)等于后一個(gè)數(shù)，且前者沒有訪問過，nums[i-1] == nums[i] && ! visited[i-1]，則直接跳過

class Solution { public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<int> row;vector<vector<int>> ans;bool occurred[nums.size()];memset(occurred, 0, sizeof(bool)*nums.size());sort(nums.begin(), nums.end());bt(nums, 0, occurred, row, ans);return ans;}void bt(vector<int>& nums, int count, bool *occurred, vector<int> row, vector<vector<int>>& ans){if(count == nums.size()){ans.push_back(row); return;}for(int i = 0; i < nums.size(); ++i){if(occurred[i] == false){if(i >= 1 && nums[i-1] == nums[i] && !occurred[i-1])continue; //搜索剪枝occurred[i] = true;row.push_back(nums[i]);bt(nums,count+1,occurred,row,ans);row.pop_back();occurred[i] = false;}}} }; class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:import itertoolsreturn list(set(itertools.permutations(nums, len(nums))))

44 ms 15.2 MB Python3

總結(jié)

以上是生活随笔為你收集整理的LeetCode 47. 全排列 II（回溯+搜索剪枝）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。