input :
- nums
output :
- nums의 원소로 만들 수 있는 모든 순열을 반환하시오.
조건 :
- 1 <= nums.length <= 6
- All the integers of nums are unique.
Solution explain : Solution1
idea
- 재귀를 통해 해결해보자.
- base case : 만든 순열의 길이가 사용해야 하는 개수와 동일해지면 ret배열에 추가한다.
- recursive case : 반복문을 통하여 사용할 수 있는 원소인지 확인한다. 사용을 하면 해당 값을 1로 변경하고 재귀를 수행한다. 돌아오면 이를 원상태로 돌려야 한다.
주의
- DP론 어떻게 할 수 있지?
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
global ret
ret = []
def recursive(used, ordered):
if len(ordered) == len(nums):
ret.append(ordered)
return
for key in used.keys():
if used[key] == 1:
continue
used[key] = 1
recursive(used, ordered + [key])
used[key] = 0
used = {item:0 for item in nums}
recursive(used, [])
return ret
