LeetCode-047-全排列 II
全排列 II
題目描述：給定一個可包含重複數字的序列 nums ，按任意順序 返回所有不重複的全排列。
示例說明請見LeetCode官網。
連結：https：//leetcode-cn。com/problems/permutations-ii/
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。
解法一：窮舉法
首先，構造一棵多叉樹MultiTree，該多叉樹有以下幾個屬性，used表示當前路徑已經走過的陣列的位置，paths表示當前路徑中的數字。
然後宣告一個佇列queue，佇列的元素就是MultiTree，首先將nums中不同的數字出初始化成路徑的第一個數字，然後加入到佇列中（需要同時初始化used和paths）。
然後遍歷佇列queue，按照類似的方式將陣列nums中沒用到的數字加入到當前路徑中（需要判斷重複數字）。
直到佇列中每一條路徑的長度都和nums的長度一樣，即已將所有的數字加入到路徑中。
最後，返回佇列中的所有的路徑paths。
說明：
其實本來想構造一棵多叉樹，所有葉子節點到根節點的路徑即為所有的路徑排列，後來沒用到，所以沒有構造樹的父子關係 。
import
java。util。*；
public
class
LeetCode_047
{
/**
* 構造一棵多叉樹
*/
static
class
MultiTree
{
// 當前的值
public
Integer val；
public
MultiTree parent；
// 當前路徑已經走過的陣列的位置
public
List
// 當前路徑中的數字
public
List
public
MultiTree
（Integer val）
{
this
。val = val；
used =
new
ArrayList<>（）；
paths =
new
ArrayList<>（）；
}
}
public
static
List
int
［］ nums） {
Queue
new
LinkedList<>（）；
Arrays。sort（nums）；
int
curNum = nums［
0
］；
// 第一條路徑
MultiTree first =
new
MultiTree（nums［
0
］）；
first。paths。add（nums［
0
］）；
first。used。add（
0
）；
queue。add（first）；
// 其他路徑
for
（
int
i =
1
； i < nums。length； i++） {
if
（nums［i］ ！= curNum） {
MultiTree next =
new
MultiTree（nums［i］）；
next。paths。add（nums［i］）；
next。used。add（i）；
queue。add（next）；
curNum = nums［i］；
}
}
int
length =
1
；
while
（length < nums。length） {
int
count = queue。size（）；
while
（count >
0
） {
MultiTree curNode = queue。poll（）；
int
firstNum = -
1
， firstNumIndex = -
1
；
// 找到第一個已有路徑沒經過的數
for
（
int
i =
0
； i < nums。length； i++） {
if
（！curNode。used。contains（i）） {
firstNum = nums［i］；
firstNumIndex = i；
MultiTree firstTree =
new
MultiTree（nums［i］）；
firstTree。paths。addAll（curNode。paths）；
firstTree。paths。add（firstNum）；
firstTree。used。addAll（curNode。used）；
firstTree。used。add（firstNumIndex）；
queue。add（firstTree）；
break
；
}
}
// 將其他不同的數也新增到新的路徑
for
（
int
i = firstNumIndex +
1
； i < nums。length； i++） {
if
（！curNode。used。contains（i） && nums［i］ ！= firstNum） {
MultiTree otherTree =
new
MultiTree（nums［i］）；
otherTree。paths。addAll（curNode。paths）；
otherTree。paths。add（nums［i］）；
otherTree。used。addAll（curNode。used）；
otherTree。used。add（i）；
queue。add（otherTree）；
firstNum = nums［i］；
}
}
count——；
}
length++；
}
List
new
ArrayList<>（）；
while
（！queue。isEmpty（）） {
result。add（queue。poll（）。paths）；
}
return
result；
}
public
static
void
main
（String［］ args）
{
int
［］ nums =
new
int
［］{
1
，
1
，
2
}；
for
（List
for
（Integer integer ： integers） {
System。out。print（integer +
“ ”
）；
}
System。out。println（）；
}
}
}
【每日寄語】
願太陽的光輝始終灑在你心上。願所有的不愉快，苦盡甘來。願每個脆弱的人都能得到善待。願現實有光，世界有暖。
