46: PERMUTATIONS

Link : https://leetcode.com/problems/permutations/

---

1. 문제

• Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
  
  Example 1:Input: nums = [1,2,3]
  Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
  Example 2:Input: nums = [0,1]
  Output: [[0,1],[1,0]]
  Example 3:Input: nums = [1]
  Output: [[1]]

 

---

2. 문제의 조건

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• 모든 정수 nums는 유일하다.

 

---

3. 문제 접근

• 아이디어
  
  해당 예제 방식을보면 [1, 2, 3]이 주어져 있을 때 점점 깊어진다는 것을 알 수 있습니다. [1] [1, 2] [1, 2, 3] 순으로 되어서 [1, 2, 3]이 정답 중 일부이죠. 이는 깊이 우선 탐색(DFS)로 해결할 수 있다는 감이옵니다!

 

---

4. 풀이 방법

• 정답 일부를 반환할 list를 선언합니다.
• 만약 남은 input이 0개일 경우 [result[:]]로 반환합니다. (정답 중 하나) [:]는 call by value로 해야함.
• 남은 input이 존재 할 경우 result[deapth]에 for로 가져온 하나를 넣고 그 부분만 뺴고 다시 DFS를 수행합니다. 그 결과를 list에 더해줍니다.
• 모든 for이 끝나면 list를 반환합니다.

 

---

5. 소스코드

• https://cjw-git.tistory.com/178

 

---

 

cjw.git@gmail.com