문제 링크 (opens new window)

문제 설명

1. 백트래킹과 원복 문제
2. 배열 주소값 전달하기
3. 요소 합이 타겟보다 커지면 더 이상 백트래킹 할 필요 없음
4. 요소 합이 타겟과 동일해지면 해당 요소 결과값에 추가하고 종료
5. 중복해서 요소를 고를 수 있으니, backtrack재귀 호출시 idx+1을 전달하지 않고 idx를 전달한다.
6. 백트래킹 완료 후 원복하고 다음 인덱스로 이동
   • [2,3,6,7]에서 합을 7로 만들어야 할때
   • [2,2,3] 합 7 만들고
   • removeLast 호출하여 [2,2] 뎁스에서 원복 후 다음으로 넘어감
   • [2,2,6] 이후 쭉 진행

class Solution {
    private func backtrack(_ start: Int, _ result: inout [[Int]], _ superCandidates: inout [Int], _ subCandidates: inout [Int], _ target: Int) {
        let candidatesSum = subCandidates.reduce(0, {$0 + $1})
        if candidatesSum == target {
            result.append(subCandidates)
            return
        }
        if candidatesSum > target {
            return
        }

        for idx in start..<superCandidates.count {
            subCandidates.append(superCandidates[idx])
            backtrack(idx, &result, &superCandidates, &subCandidates, target)
            _ = subCandidates.removeLast()
        }
    }

    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var result: [[Int]] = []
        var subCandidates: [Int] = []
        var candidates = candidates
        backtrack(0, &result, &candidates, &subCandidates, target)
        return result
    }
}