LeetCode | 46. Permutations (Medium) - Swift

46. Permutations

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]]

 

---

 

Swift로 순열을 구하는 코드를 찾다가 풀게 된 문제!

(Swift에서는 순열, 조합을 일일이 구해야 하기 때문에..한 번 제대로 정리할 겸 문제도 풀어보았다.)

 

생각 과정

만약 [1, 2, 3]이라는 배열의 순열을 구해야한다고 생각해보자.

아직 담기지 않은(visited == false) 숫자를 담는 걸 반복해서 총 3 길이의 배열이 배출되면 성공이다.

배열이 완성되었다면 담겼다는 표시(visited == true)를 다시 담기지 않음으로 바꾼 뒤, 그 다음 숫자로 넘어간다. (일종의 DFS라고도 볼 수 있겠다.)

배출된 배열들을 한데 모으면 모든 순열을 구할 수 있다.

 

풀이 과정

permutation이라는 함수를 만들어 이 함수를 재귀 호출할 것이다.

class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = [] // 모든 순열을 저장하는 result
        var visited = [Bool](repeating: false, count: nums.count) // 방문했는지 확인하는 visited
        
        func permutation(_ temp: [Int]) { 
            if temp.count == nums.count { // 순열의 길이가 원본 배열의 길이와 같다면 순열이 완성된 것이므로 result에 추가(배출)
                result.append(temp)
            }
            
            for i in 0...nums.count - 1 {
                if visited[i] == true { // 이미 방문한 숫자라면 continue
                    continue
                } else { // 방문하지 않은 숫자라면 순열에 포함(방문했음을 체크)하여 그 뒷부분 순열을 구하기
                    visited[i] = true 
                    permutation(temp + [nums[i]]) 
                    visited[i] = false // 뒷부분이 모두 완료되었다면 방문했음을 체크 해제하여 다음 숫자로 넘어가기
                }
            }
            
        }
        permutation([]) // 빈 순열로 시작해 0번째 인덱스부터 채워나간다
        
        return result
    }
}

 

 

 

 

---

참고

https://icksw.tistory.com/180