[LeetCode/Kotlin]Medium - 39. Combination Sum

Combination Sum - LeetCode

문제

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the

frequency

of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

풀이

나의 풀이법

풀이 접근 과정

그냥 큰 고민 없이 바로 문제 풀이 시작하고 바로 통과…

최종 소스코드

class Solution {
    val answer: ArrayList<ArrayList<Int>> = arrayListOf()

    fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
        cumulativeSum(candidates, target, 0, arrayListOf<Int>(), 0)
        return answer
    }

    private fun cumulativeSum(candidates: IntArray, target: Int, sum: Int, arr: ArrayList<Int>, index: Int) {
        candidates.forEachIndexed { idx, it->
            if (idx < index) return@forEachIndexed

            val newArr = arrayListOf<Int>()
            newArr.addAll(arr)

            if (sum+it < target) {
                newArr.add(it)
                cumulativeSum(candidates, target, sum+it, newArr, idx)
            } else if (sum+it == target) {
                newArr.add(it)
                answer.add(newArr)
            }
        }
    }
}

다른 풀이법

fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val currentList = mutableListOf<Int>()

    // candidates 배열을 정렬하여 순서대로 조합을 생성하기 위해 준비
    candidates.sort()

    fun backtrack(start: Int, remain: Int) {
        if (remain == 0) {
            // 현재 조합이 목표 합계와 일치하면 결과에 추가
            result.add(ArrayList(currentList))
            return
        }

        for (i in start until candidates.size) {
            val num = candidates[i]
            if (num > remain) {
                // 현재 숫자가 남은 합계를 초과하면 중단
                break
            }

            // 현재 숫자를 현재 조합에 추가
            currentList.add(num)

            // 재귀적으로 다음 숫자 선택
            backtrack(i, remain - num)

            // 현재 숫자를 다시 제거 (다른 조합을 위해)
            currentList.removeAt(currentList.size - 1)
        }
    }

    // 재귀 호출을 시작
    backtrack(0, target)

    return result
}

---

Comment

비교적 쉬운 문제였다 !!