[LeetCode] 46. Permutations & 47. Permutations II

• Total Accepted: 154997
• Total Submissions: 370049
• Difficulty: Medium
• Contributor: LeetCode

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

找出數字的全部組合, 用dfs 搜尋

 在dfs的時候 每次把自己的數值加到 path 裡

然後對剩下的nums 繼續做dfs. 一旦path長度等於nums的長度 就把path 加到res去

 line 13: 傳入nums並且排除nums[i] , 記得要用深copy 傳path給下一個dfs

 

DFS 走的順序

nums:  [1, 2, 3]

path:  []

res:   []

nums:  [2, 3]

path:  [1]

res:   []

nums:  [3]

path:  [1, 2]

res:   []

nums:  []

path:  [1, 2, 3]

res:   []

nums:  [2]

path:  [1, 3]

res:   [[1, 2, 3]]

nums:  []

path:  [1, 3, 2]

res:   [[1, 2, 3]]

nums:  [1, 3]

path:  [2]

res:   [[1, 2, 3], [1, 3, 2]]

nums:  [3]

path:  [2, 1]

res:   [[1, 2, 3], [1, 3, 2]]

nums:  []

path:  [2, 1, 3]

res:   [[1, 2, 3], [1, 3, 2]]

nums:  [1]

path:  [2, 3]

res:   [[1, 2, 3], [1, 3, 2], [2, 1, 3]]

nums:  []

path:  [2, 3, 1]

res:   [[1, 2, 3], [1, 3, 2], [2, 1, 3]]

nums:  [1, 2]

path:  [3]

res:   [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]

nums:  [2]

path:  [3, 1]

res:   [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]

nums:  []

path:  [3, 1, 2]

res:   [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]

nums:  [1]

path:  [3, 2]

res:   [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]]

nums:  []

path:  [3, 2, 1]

res:   [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]]

47. Permutations II

如果有重複的 element 怎麼辦?

解決方法是, 這裡加兩個部分

1) 對 nums 排個序, 這樣重複的部分 一定相鄰

line_21

2) 加一個 flag, 判斷當前的數字是否重複過. 如果重複過就跳過不跑 dfs 了

line_12, line_14, line_15