input :
- nums
output :
- 만들 수 있는 유일한 순열들을 반환하시오.
조건 :
- 1 <= nums.length <= 8
Solution explain : Solution1
idea
- 재귀를 한다고 해도 8!이니까 재귀를 수행하자.
- 중복을 확인하기 위해서 딕셔너리의 키를 나중에 반환값으로 리턴한다.
- base case : 만들어진 문자의 개수, 사용해야 하는 문자의 개수가 동일한 경우 키를 튜플로 전환하여 저장한다.
- recursive case : 반복문을 통해 사용할 수 있는 모든 문자열을 쓴다. 사용할 수 있는 여부는 개수를 기록하도록 하여 1씩 차감을 하도록 한다.
주의
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
global ret
ret = dict()
def recursive(used, ordered):
if len(ordered) == len(nums):
ret[tuple(ordered)] = 1
return
for key in used.keys():
if used[key] <= 0:
continue
used[key] -= 1
recursive(used, ordered + [key])
used[key] += 1
used = {item:0 for item in nums}
for item in nums:
used[item] += 1
recursive(used, [])
return ret