순열(Permutation) 구하기 with kotlin

1, 2, 3 이라는 배열이 주어졌을때 해당 element 에 대해서 permutation 을 구한다고 가정해봅시다.

 

경우의 수는

총 6 가지 입니다 6개의 경우의 수가 나온는 것을 증명 하려면 

• 첫번째 자리수에 올수 있는 것들은 총 [1, 2, 3] 세가지 중 하나 입니다.
• 두번째 자리수에 올수 있는 것들은 첫번째 를 제외한 총 두가지 중 하나 입니다.
• 세번째 자리수에 올수 있는 것들은 첫번째 두번째를 제외한 총 한가지 입니다.
• 3 * 2 * 1 = 6 

경우의 수를 구하는 대표적인 방법은 backtracking 입니다.

 

 

해당 Tree 를 코드로 구현해보면 다음과 같습니다.

 

fun solution(nums: IntArray): Unit {
    val endpoint = nums.size

    val result = mutableListOf<List<Int>>()
    fun permutation(level: Int, permutationList: MutableList<Int>) {
	// 재귀를 끝내는 조건
    	if (permutationList.size == endpoint) {
        }
         
        for (num in nums) {
        }
    }
}

 

nums = [1, 2, 3] 이라는 가정하에 nums 의 size 와 크기가 똑같을 때 까지 permutation method 을 recursion 하고 끝냅니다.

 

num in nums 에서는 해당 숫자가 permutationList 에 들어있지 않으면 level + 1 증가 시키고 permutationList 에 num 을 추가 한뒤

자기 자신을 호출합니다.

그리고 permutationList 를 파라미터로 넘기고 있기 때문에 참조 가 발생하여 permutation 이 종료되고 난뒤에는 
num 을 permutationList 에서 remove 합니다

 

if (permutationList.size == endpoint) {
    result.add(permutationList.toMutableList())
    return
}

for (num in nums) {
    if (!permutationList.contains(num)) {
        permutationList.add(num)
        permutation(level + 1, permutationList)
        permutationList.remove(num)
    }
}

 

해당 문제는 leet code 46번 입니다

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

Permutations - LeetCode