[leetcode 78] Subsets

78. Subsets

https://leetcode.com/problems/subsets/

해결 과정

BackTracking 을 사용하여 풀었다.

1. 입력 nums 가 [1,2,3] 일 때, 아래와 같은 순서로 검색하게된다.

-> [] [1] [1,2] [1,2,3] [1,3] [2] [2,3] [3]

    0
    []

    0..2
    [1]     1..2
            [1,2]   2..2
                    [1,2,3]    3//
                    
                    [1,2](X)
            [1](X)
            [1,3]
    
    1..2
    [2]     2..2
            [2,3]   
                    3//
            [2](X)

    2..2
    [3]   

2. 입력 nums 가 [1,2,3,4] 일 때는 아래와 같은 순서로 검색하게된다.

-> [] [1] [1,2] [1,2,3] [1,2,3,4] [1,2,4] [1,3], [1,3,4], [1,4], [2], [2,3], [2,3,4], [2,4], [3], [3,4], [4]

0
[]

0..3
[1]     1..3
        [1,2]   2..3
                [1,2,3]     3..3
                            [1,2,3,4]   4//
                            [1,2,3](X)
                [1,2](X)
                [1,2,4]
        [1](X)
        [1,3]   
                [1,3,4]
                [1,3](X)                
        [1](X)
        [1,4]

1..3
[2]     2..3
        [2,3]   3..3
                [2,3,4]     4//
                [2,3](X)
        [2](X)
        [2,4]

2..3
[3]     3..3
        [3,4]   4//

3..3
[4]

코드

fun subsets(nums: IntArray): List<List<Int>> {
    val result: MutableList<List<Int>> = ArrayList()
    backtrack(0, ArrayList(), result, nums)
    return result
}

// 시작 idx, 현재 list, 결과 list, 최초입력 list 
private fun backtrack(start: Int, curr: MutableList<Int>, 
                        result: MutableList<List<Int>>, nums: IntArray) {
    result.add(ArrayList(curr))
    for (i in start until nums.size) {
        curr.add(nums[i])                   //  현재 조합
        backtrack(i+1, curr, result, nums)  //  다음 조합
        curr.removeAt(curr.size-1)          //  back (성공하기 직전으로 상태 되돌리기)
    }
}

배운 점

백트래킹(BackTracking)

• 성공하기 직전으로 상태로 되돌리며 (back) 검색하는 방법.
• 한정조건 (CSP: Constraint Satisfaction Problems)을 이용한 검색 방법으로, 모든 경우의 수를 검색하는 것 보다 경우의 수가 적어진다.