[LeetCode] 46번 - Permutations [Swift]

문제 링크

Permutations - LeetCode

문제 

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

 

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

문제 풀이

이 문제는 주어진 정수들로 만들 수 있는 모든 순열을 구하는 문제입니다.

똑같은 값이 여러번 들어가면 안되기 때문에 중복체크를 해줘야하는게 가장 중요한 아이디어 입니다.

 

일반적인 백트래킹을 수행하는데, 이미 사용한 숫자인지에 대한 체크만 처리해주시면 됩니다.

그리고 return 한 뒤에는 방문여부를 초기화 해줘야 모든 순열을 구할 수 있습니다! 

 

소스 코드

class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        
        var result: [[Int]] = []
        // 중복을 허용하지 않게 만들어야 하므로 아래와 같이 사용여부를 체크해줍니다.
        var visited: [Bool] = [Bool](repeating: false, count: nums.count)
        
        func permutation(_ nowPermute: [Int]) {
            // 만약 현재 순열의 원소 수가 주어진 원소수와 같다면 결과에 추가!
            if nowPermute.count == nums.count {
                result.append(nowPermute)
                return
            }
            
            for i in 0..<nums.count {
                // 이미 사용한 값이라면 넘어갑니다.
                if visited[i] {
                    continue
                } else {
                    visited[i] = true
                    permutation(nowPermute + [nums[i]])
                    visited[i] = false
                }
            }
        }
        
        permutation([])
        
        return result
    }
}